Merge Intervals

Q: Berapa kompleksitas waktu Merge Intervals?

Solusi pengurutan dan sweep berjalan dalam waktu O(n log n) untuk n interval: pengurutan memerlukan O(n log n) dan sweep memerlukan O(n). Solusi ini menggunakan ruang tambahan O(n) untuk pasangan yang sudah diurutkan dan hasilnya.

Q: Mengapa interval diurutkan berdasarkan waktu mulai, bukan waktu selesai?

Jika diurutkan berdasarkan titik awal, sebuah interval hanya bisa tumpang tindih dengan grup yang sedang kamu buat, jadi satu perbandingan dengan titik akhir grup tersebut menentukan semuanya. Jika diurutkan berdasarkan titik akhir, interval berikutnya bisa dimulai sebelum grup yang sudah kamu tutup: [5, 6] muncul sebelum [1, 10] , dan pemindaian maju akan keliru mempertahankan 5 sebagai titik awal.

Q: Bisakah kamu merge interval tanpa ruang tambahan?

Ya, jika kamu boleh mengubah input. Urutkan interval langsung, lalu tulis setiap interval yang digabungkan di bagian depan array yang sama dan simpan indeks interval terakhir yang ditulis. Waktunya tetap O(n log n), dan satu-satunya ruang tambahan adalah yang digunakan oleh pengurutan dalam bahasamu.

SedangInterval Pengurutan

+10

Kamu mendapatkan sekumpulan interval, masing-masing berupa rentang bilangan bulat dari awal hingga akhir. Gabungkan setiap kelompok interval yang saling tumpang tindih menjadi satu interval yang mencakup seluruh kelompok, lalu kembalikan interval hasil penggabungan yang diurutkan berdasarkan nilai awal. Interval yang hanya bersentuhan, seperti [1, 4] dan [4, 5], dianggap saling tumpang tindih.

Interval diberikan dalam dua array dengan panjang yang sama: interval i adalah [starts[i], ends[i]]. Kamu mengembalikan array 2D, yaitu daftar pasangan [start, end].

Fungsi

mergeIntervals(starts: integer-array, ends: integer-array) → integer-2d-array

startsinteger-array: awal setiap interval
endsinteger-array: ujung setiap interval, pada indeks yang sama dengan awalnya
Mengembalikaninteger-2d-array: interval yang telah digabungkan dalam bentuk pasangan [start, end], diurutkan berdasarkan start

Batasan

1 ≤ starts.length == ends.length ≤ 10⁴
0 ≤ starts[i] ≤ ends[i] ≤ 10⁴
Interval tiba dalam urutan apa pun.
Interval yang hanya bersentuhan di ujungnya dianggap saling tumpang tindih.

Contoh

Input: starts = [5, 1, 12, 3]ends = [7, 4, 14, 6]
Output: [[1, 7], [12, 14]]
Penjelasan: Urut berdasarkan waktu mulai, [1, 4] bertumpang tindih dengan [3, 6], yang bertumpang tindih dengan [5, 7], sehingga ketiganya menjadi [1, 7]. [12, 14] dimulai setelah 7 dan tetap terpisah.

Pertanyaan lanjutan

Interval sudah diberikan dalam keadaan digabungkan dan diurutkan berdasarkan titik awalnya, dan kamu harus menambahkan satu interval baru. Bisakah kamu mengembalikan list yang sudah digabungkan dalam waktu O(n), tanpa mengurutkannya lagi?

Solusi

Menggabungkan pasangan dalam urutan apa pun memerlukan beberapa kali pemindaian, karena setiap penggabungan memperlebar interval dan membuatnya menjangkau interval yang sudah kamu periksa. Sebagai gantinya, urutkan berdasarkan titik awal. Dengan begitu, sebuah interval hanya dapat bertumpang tindih dengan kelompok yang sedang kamu susun, dan satu kali pemindaian cukup untuk menyelesaikannya.

Gabungkan pasangan yang tumpang tindih sampai tidak ada lagi perubahan

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Interval [a, b] dan [c, d] tumpang tindih jika c ≤ b dan a ≤ d, dan [min(a, c), max(b, d)] mencakup keduanya. Setiap penggabungan menghapus satu interval, jadi prosesnya berhenti, dan setelah satu putaran penuh tidak menemukan tumpang tindih, tidak ada dua interval yang tersisa yang berbagi titik. Satu putaran saja tidak cukup: interval hasil penggabungan lebih lebar dan kini dapat menjangkau interval yang sebelumnya dibandingkan dengan bagian yang lebih kecil darinya selama putaran tersebut.

Satu putaran membandingkan sekitar n²/2 pasangan, dan kamu mungkin perlu hingga n putaran: O(n³). Satu putaran untuk 10^4 interval saja sudah memerlukan 5 × 10^7 perbandingan.

Algoritma

Salin starts dan ends, lalu simpan jumlah interval aktif dalam n.
Bandingkan setiap interval i dengan semua interval setelahnya j. Jika keduanya tumpang tindih, rentangkan i agar mencakup j, pindahkan interval aktif terakhir ke slot j, lalu kurangi n sebanyak satu.
Setelah penggabungan, periksa kembali slot j, karena sekarang ada interval lain di sana.
Ulangi putaran hingga tidak ada penggabungan.
Pasangkan setiap nilai awal yang masih aktif dengan nilai akhirnya, urutkan pasangan berdasarkan nilai awal, lalu kembalikan pasangan tersebut.

def mergeIntervals(starts, ends):
    s = list(starts)
    e = list(ends)
    n = len(s)
    changed = True
    while changed:
        changed = False
        i = 0
        while i < n:
            j = i + 1
            while j < n:
                if s[j] <= e[i] and s[i] <= e[j]:
                    # Intervals i and j overlap: interval i absorbs interval j.
                    s[i] = min(s[i], s[j])
                    e[i] = max(e[i], e[j])
                    # Move the last interval into slot j and drop the last slot.
                    n -= 1
                    s[j] = s[n]
                    e[j] = e[n]
                    changed = True
                else:
                    j += 1
            i += 1
    return sorted([s[k], e[k]] for k in range(n))

Urutkan berdasarkan titik awal, lalu lakukan sweep sekali

Intuisi

Setelah diurutkan berdasarkan titik awal, interval berikutnya dimulai tidak lebih awal dari interval mana pun dalam kelompok terakhir, yang berakhir di e. Jika titik awalnya paling jauh sama dengan e, interval itu tumpang tindih atau bersentuhan dengan kelompok tersebut dan bergabung dengannya, lalu e menjadi nilai yang lebih besar di antara kedua titik akhir. Jika titik awalnya melewati e, tidak ada interval setelahnya yang dapat menjangkau kembali kelompok tersebut, karena interval berikutnya dimulai lebih jauh ke kanan. Kelompok itu selesai, dan interval tersebut membuka kelompok baru.

Pengurutan membutuhkan O(n log n), dan proses sweep mengunjungi setiap interval satu kali. Kelompok ditutup dari kiri ke kanan, sehingga hasilnya tersusun berdasarkan titik awal.

Algoritma

Pasangkan setiap awal dengan akhirnya: interval i adalah [starts[i], ends[i]].
Urutkan pasangan berdasarkan awal.
Telusuri pasangan yang sudah diurutkan. Jika hasilnya kosong, atau pasangan tersebut dimulai setelah akhir interval terakhir yang digabungkan, tambahkan pasangan tersebut sebagai interval baru.
Jika tidak, tetapkan akhir interval terakhir yang digabungkan ke nilai yang lebih besar antara akhirnya dan akhir pasangan tersebut.
Kembalikan list yang sudah digabungkan.

def mergeIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            if end > merged[-1][1]:
                merged[-1][1] = end
        else:
            merged.append([start, end])
    return merged

Jebakan dan kasus tepi

Membandingkan dengan <, bukan ≤. Interval yang bersentuhan seperti [1, 4] dan [4, 5] harus digabung.
Mengatur akhir ke akhir interval baru, bukan ke nilai yang lebih besar di antara keduanya. [1, 10] yang diikuti [2, 3] harus tetap menjadi [1, 10].
Mengurutkan starts sendiri, lalu membaca ends pada posisi baru, sehingga suatu awal mendapat akhir dari interval lain. Pasangkan keduanya terlebih dahulu, atau urutkan indeks.
Membandingkan dengan interval masukan sebelumnya, bukan interval terakhir yang telah digabung. Dalam [1, 10], [2, 3], [4, 5], interval ketiga berada di dalam [1, 10], meskipun tidak bersentuhan dengan [2, 3].
Dalam C, tidak mengatur *returnSize ke jumlah interval yang telah digabung dan setiap ukuran kolom ke 2.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Merge Intervals?

Solusi pengurutan dan sweep berjalan dalam waktu O(n log n) untuk n interval: pengurutan memerlukan O(n log n) dan sweep memerlukan O(n). Solusi ini menggunakan ruang tambahan O(n) untuk pasangan yang sudah diurutkan dan hasilnya.

Mengapa interval diurutkan berdasarkan waktu mulai, bukan waktu selesai?

Jika diurutkan berdasarkan titik awal, sebuah interval hanya bisa tumpang tindih dengan grup yang sedang kamu buat, jadi satu perbandingan dengan titik akhir grup tersebut menentukan semuanya. Jika diurutkan berdasarkan titik akhir, interval berikutnya bisa dimulai sebelum grup yang sudah kamu tutup: [5, 6] muncul sebelum [1, 10], dan pemindaian maju akan keliru mempertahankan 5 sebagai titik awal.

Bisakah kamu merge interval tanpa ruang tambahan?

Ya, jika kamu boleh mengubah input. Urutkan interval langsung, lalu tulis setiap interval yang digabungkan di bagian depan array yang sama dan simpan indeks interval terakhir yang ditulis. Waktunya tetap O(n log n), dan satu-satunya ruang tambahan adalah yang digunakan oleh pengurutan dalam bahasamu.

def mergeIntervals(starts, ends):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

starts = [5, 1, 12, 3]
ends = [7, 4, 14, 6]

Output yang diharapkan

[[1, 7], [12, 14]]