Non-overlapping Intervals

Q: Apa kompleksitas waktu dari Interval yang Tidak Saling Tumpang Tindih?

Solusi greedy mengurutkan berdasarkan waktu akhir dalam O(n log n) dan menelusuri interval satu kali, sehingga totalnya adalah O(n log n) dengan ruang O(n) untuk salinan yang sudah diurutkan. Versi pemrograman dinamis memiliki kompleksitas O(n²) , sedangkan mencoba setiap himpunan yang akan dipertahankan memiliki kompleksitas O(2^n) .

SedangInterval Greedy

+10

Interval i berlangsung dari starts[i] hingga ends[i]. Kembalikan jumlah interval paling sedikit yang harus kamu hapus agar tidak ada dua interval yang tersisa saling tumpang tindih. Dua interval yang hanya bersentuhan, yaitu saat satu interval berakhir tepat di titik interval lainnya dimulai, tidak saling tumpang tindih.

Fungsi

eraseOverlapIntervals(starts: integer-array, ends: integer-array) → integer

startsinteger-array: awal setiap interval
endsinteger-array: akhir setiap interval, pada indeks yang sama dengan awalnya
Mengembalikaninteger: interval sesedikit mungkin yang harus dihapus agar sisanya tidak saling tumpang tindih

Batasan

1 ≤ starts.length == ends.length ≤ 5000
-5 × 10⁴ ≤ starts[i] < ends[i] ≤ 5 × 10⁴
Interval tidak diurutkan. Dua interval bisa identik.

Contoh

Input: starts = [3, 1, 5, 2]ends = [6, 4, 7, 3]
Output: 2
Penjelasan: Dalam urutan awal, intervalnya adalah [1,4], [2,3], [3,6], dan [5,7]. Pertahankan [2,3] dan [3,6], yang hanya bersentuhan, lalu hapus 2 lainnya. Tiga interval tidak bisa dipertahankan: [1,4] tumpang tindih dengan [2,3], dan [3,6] tumpang tindih dengan [5,7].

Input: starts = [0, 0, 0]ends = [5, 5, 5]
Output: 2
Penjelasan: Ketiga interval berada pada [0,5], jadi setiap dua interval saling tumpang tindih. Satu tetap, dan kamu menghapus 2.

Input: starts = [4, 1, 2]ends = [6, 2, 4]
Output: 0
Penjelasan: [1,2], [2,4], dan [4,6] bertemu di ujung dan tidak pernah tumpang tindih, jadi kamu tidak menghapus apa pun dan jawabannya adalah 0.

Pertanyaan lanjutan

Misalkan setiap interval memiliki nilai dan kamu ingin mendapatkan total nilai terbesar dari interval-interval yang tidak tumpang tindih. Apakah memilih interval yang berakhir paling awal masih berhasil?

Solusi

Menghapus interval sesedikit mungkin sama dengan mempertahankan interval sebanyak mungkin yang tidak saling tumpang tindih: jawabannya adalah n dikurangi jumlah tersebut. Satu aturan greedy menemukan jumlahnya dalam O(n log n): dari interval yang masih muat, selalu pertahankan interval yang berakhir paling awal.

Pertahankan atau hapus setiap interval

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Urutkan interval berdasarkan titik awal, lalu tentukan apakah setiap interval akan dipertahankan atau dihapus. Kamu hanya boleh mempertahankannya jika interval tersebut dimulai pada atau setelah titik akhir interval terakhir yang dipertahankan, sehingga interval yang dipertahankan membentuk rangkaian tanpa tumpang tindih. Coba kedua pilihan untuk setiap interval dan ambil jumlah yang lebih besar. Jawabannya adalah n dikurangi jumlah tersebut.

Setiap interval dapat menggandakan jumlah cabang, sehingga n interval menghasilkan hingga 2^n jalur. Tiga puluh interval yang tidak tumpang tindih saja sudah berarti lebih dari satu miliar pemanggilan, sedangkan n bisa mencapai 5000.

Algoritma

Urutkan interval berdasarkan titik awal, dengan setiap titik awal tetap berpasangan dengan titik akhirnya.
Definisikan mostKept(i, last): jumlah interval terbanyak yang bisa kamu pertahankan mulai dari posisi i, saat last adalah interval terakhir yang dipertahankan (-1 jika tidak ada).
Jika sudah melewati akhir, kembalikan 0. Jika tidak, ambil mostKept(i+1, last), yang menghapus interval i.
Jika interval i dimulai pada atau setelah akhir last, coba juga 1 + mostKept(i+1, i) dan pertahankan nilai yang lebih besar.
Kembalikan n dikurangi mostKept(0, -1).

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))  # by start time
    n = len(intervals)

    def most_kept(i, last):
        # The most intervals you can keep among i..n-1, when interval last
        # is the latest one kept so far (-1: nothing kept yet).
        if i == n:
            return 0
        best = most_kept(i + 1, last)  # remove interval i
        if last == -1 or intervals[i][0] >= intervals[last][1]:
            best = max(best, 1 + most_kept(i + 1, i))  # keep interval i
        return best

    return n - most_kept(0, -1)

Rantai terpanjang dengan pemrograman dinamis

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Pencarian terus mengajukan pertanyaan yang sama: berapa panjang rantai terpanjang yang berakhir dengan interval ini? Jawab sekali untuk setiap interval. Urutkan berdasarkan waktu mulai, lalu anggap chain[i] sebagai jumlah interval terbanyak yang bisa kamu pertahankan dengan interval i sebagai interval terakhir.

Interval yang bisa berada tepat sebelum i berakhir pada atau sebelum starts[i], jadi interval itu dimulai lebih awal dan berada lebih awal dalam urutan yang sudah diurutkan. Dengan begitu, chain[i] = 1 + chain[j] untuk j terbaik yang memenuhi syarat, atau 1 jika tidak ada yang cocok. Pada contoh pertama, nilainya adalah 1, 1, 2, dan 2, jadi kamu mempertahankan 2 dan menghapus 2.

Perulangan bersarang melakukan n(n-1)/2 pemeriksaan: sekitar 12.5 juta saat n = 5000.

Algoritma

Urutkan interval berdasarkan awalnya, dengan tetap memasangkan setiap awal dengan akhirnya.
Tetapkan chain[i] = 1 untuk setiap interval.
Untuk setiap i dan setiap j < i dengan ends[j] ≤ starts[i], tetapkan chain[i] menjadi chain[j]+1 jika nilai itu lebih besar.
Kembalikan n dikurangi nilai terbesar dalam chain.

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))  # by start time
    n = len(intervals)
    # chain[i]: the most intervals you can keep when interval i is the last one kept
    chain = [1] * n
    for i in range(n):
        for j in range(i):
            if intervals[j][1] <= intervals[i][0] and chain[j] + 1 > chain[i]:
                chain[i] = chain[j] + 1
    return n - max(chain)

Greedy: pertahankan interval yang berakhir lebih dulu

Intuisi

Ambil interval dengan titik akhir terkecil. Salah satu solusi optimal mempertahankannya: dalam himpunan terbesar yang bisa kamu pertahankan, ganti interval paling awal dengan interval ini. Titik akhirnya tidak lebih akhir, jadi interval ini tetap berakhir pada atau sebelum awal interval berikutnya yang dipertahankan, dan ukuran himpunan tetap sama tanpa tumpang tindih. Setiap interval yang dimulai sebelum titik akhirnya bertumpang tindih dengannya dan harus dihapus. Interval yang tersisa membentuk masalah yang sama, tetapi hanya pada interval yang dimulai pada atau setelah titik akhir tersebut.

Pada contoh pertama, setelah diurutkan berdasarkan titik akhir, kamu mempertahankan [2,3], menghapus [1,4], mempertahankan [3,6], lalu menghapus [5,7]. Mempertahankan interval terpendek justru gagal pada [1,5], [4,7], [6,10]: [4,7] bertumpang tindih dengan kedua interval lainnya dan mengharuskan dua interval dihapus, padahal satu saja sudah cukup.

Pengurutan membutuhkan O(n log n) dan penelusuran membutuhkan O(n).

Algoritma

Urutkan interval berdasarkan titik akhirnya, dengan menjaga setiap titik akhir tetap bersama titik awalnya.
Pertahankan interval pertama: atur lastEnd ke titik akhirnya dan removed ke 0.
Untuk setiap interval berikutnya, jika interval tersebut dimulai pada atau setelah lastEnd, pertahankan interval tersebut dan atur lastEnd ke titik akhirnya.
Jika tidak, tambahkan 1 ke removed.
Kembalikan removed.

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(ends, starts))  # by end time
    removed = 0
    last_end = intervals[0][0]  # the interval that ends first is always kept
    for end, start in intervals[1:]:
        if start >= last_end:
            last_end = end  # it fits after the last kept interval: keep it
        else:
            removed += 1  # it overlaps the last kept interval: remove it
    return removed

Jebakan dan kasus tepi

Menganggap interval yang bersentuhan sebagai interval yang tumpang tindih. Dengan start > lastEnd alih-alih start ≥ lastEnd, rangkaian [1,2], [2,4], [4,6] menghasilkan 1, bukan 0.
Mengurutkan berdasarkan titik awal dan mempertahankan interval yang lebih awal saat terjadi tumpang tindih. Interval lebar [0,100] kemudian menyingkirkan [1,2], [3,4], dan [5,6]: tiga interval dihapus, bukan satu.
Membandingkan setiap interval dengan interval tetangganya dalam daftar yang sudah diurutkan, bukan dengan interval terakhir yang dipertahankan. Pada contoh pertama, [3,6] harus dibandingkan dengan titik akhir [2,3], bukan dengan titik akhir [1,4] yang dihapus, atau hasilnya menjadi 3.
Mengurutkan starts dan ends sebagai dua daftar terpisah. Setiap titik akhir harus tetap berpasangan dengan titik awalnya.
Mengembalikan jumlah interval yang kamu pertahankan, bukan jumlah interval yang kamu hapus.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dari Interval yang Tidak Saling Tumpang Tindih?

Solusi greedy mengurutkan berdasarkan waktu akhir dalam O(n log n) dan menelusuri interval satu kali, sehingga totalnya adalah O(n log n) dengan ruang O(n) untuk salinan yang sudah diurutkan. Versi pemrograman dinamis memiliki kompleksitas O(n²), sedangkan mencoba setiap himpunan yang akan dipertahankan memiliki kompleksitas O(2^n).

Bisakah kamu mengurutkan berdasarkan waktu mulai?

Ya, dengan aturan berbeda untuk tumpang tindih. Telusuri interval berdasarkan waktu mulai, dan saat interval berikutnya tumpang tindih dengan interval terakhir yang dipertahankan, hitung satu penghapusan dan pertahankan interval yang berakhir lebih awal. Cara ini menghasilkan jumlah yang sama dalam waktu O(n log n) yang sama.

Apakah masalah Interval yang Tidak Saling Tumpang Tindih sama dengan masalah pemilihan aktivitas?

Ini adalah sisi lainnya. Pemilihan aktivitas mencari jumlah interval terbanyak yang tidak tumpang tindih; masalah ini mencari jumlah paling sedikit yang harus dihapus, yaitu n dikurangi jumlah tersebut. Aturan greedy yang sama, pertahankan aktivitas yang berakhir lebih awal, menyelesaikan keduanya.

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

Tes #1

Tes #2

Tes #3

Argumen

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

Output yang diharapkan

Non-overlapping Intervals

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Pertahankan atau hapus setiap interval

Rantai terpanjang dengan pemrograman dinamis

Greedy: pertahankan interval yang berakhir lebih dulu

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa