Activity Selection Problem

Q: Berapa kompleksitas waktu masalah pemilihan aktivitas?

Mengurutkan berdasarkan waktu selesai membutuhkan O(n log n) , dan proses greedy setelahnya membutuhkan O(n) , jadi pengurutanlah yang paling memakan waktu. Jika aktivitas sudah diurutkan berdasarkan waktu selesai, proses itu saja cukup untuk menyelesaikannya dalam waktu O(n) dan ruang tambahan O(1) .

MudahGreedy Pengurutan

+10

Aktivitas i berlangsung dari waktu start[i] hingga waktu finish[i]. Satu orang melakukan satu aktivitas pada satu waktu, dan aktivitas berikutnya harus dimulai setelah aktivitas sebelumnya selesai: aktivitas yang dimulai tepat saat aktivitas lain selesai tidak dapat dilakukan setelahnya.

Kembalikan jumlah aktivitas terbanyak yang dapat dilakukan satu orang.

Fungsi

maxActivities(start: integer-array, finish: integer-array) → integer

startinteger-array: waktu mulai setiap aktivitas
finishinteger-array: waktu selesai setiap aktivitas; finish[i] termasuk dalam start[i]
Mengembalikaninteger: jumlah aktivitas terbanyak yang dapat dilakukan seseorang, satu demi satu

Batasan

1 ≤ start.length == finish.length ≤ 5000
0 ≤ start[i] ≤ finish[i] ≤ 10⁵
Sebuah aktivitas dapat dimulai dan selesai pada waktu yang sama. Array tidak diurutkan.

Contoh

Input: start = [10, 12, 20, 14, 25, 21]finish = [13, 16, 24, 19, 30, 22]
Output: 4
Penjelasan: Melakukan 10 sampai 13, 14 sampai 19, 21 sampai 22, dan 25 sampai 30 menghasilkan 4. Lima tidak mungkin: 10 sampai 13 bertabrakan dengan 12 sampai 16, dan 21 sampai 22 bertabrakan dengan 20 sampai 24.

Input: start = [1, 5, 9]finish = [5, 9, 12]
Output: 2
Penjelasan: Aktivitas dari 5 hingga 9 dimulai tepat saat aktivitas pertama selesai, jadi aktivitas itu tidak bisa dilakukan setelahnya. Melakukan aktivitas dari 1 hingga 5 lalu dari 9 hingga 12 bisa dilakukan, jadi jawabannya adalah 2.

Input: start = [0, 2, 5, 8]finish = [100, 4, 7, 10]
Output: 3
Penjelasan: Aktivitas dari 0 hingga 100 bertumpang tindih dengan semua aktivitas lainnya. Jika aktivitas itu dihilangkan, 2 hingga 4, 5 hingga 7, dan 8 hingga 10 dapat disusun berurutan: 3.

Pertanyaan lanjutan

Dua orang kini bekerja secara bersamaan, masing-masing mengerjakan satu aktivitas pada satu waktu. Berapa banyak aktivitas yang dapat mereka lakukan bersama, dan siapa yang sebaiknya mengerjakan masing-masing aktivitas?

Solusi

Mencoba setiap subset aktivitas membutuhkan waktu eksponensial. Satu aturan greedy dapat menjawab pertanyaan ini: di antara aktivitas yang masih muat, selalu pilih aktivitas yang selesai paling awal. Mengurutkan berdasarkan waktu selesai mengubah aturan itu menjadi satu kali penelusuran.

Pilih waktu selesai paling awal, berulang kali

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Kegiatan yang selesai paling awal setidaknya sama baiknya untuk dipilih pertama seperti kegiatan lainnya. Kegiatan itu selesai tidak lebih lambat, jadi apa pun yang bisa dilakukan setelah pilihan pertama lainnya juga bisa dilakukan setelah kegiatan ini, dan menggantinya tidak mengubah jumlahnya. Setelah memilih kegiatan itu, masalah yang sama berulang pada kegiatan yang dimulai setelah kegiatan tersebut selesai.

Pada contoh pertama, kamu memilih 10 hingga 13, lalu 14 hingga 19, lalu 21 hingga 22, lalu 25 hingga 30: empat kegiatan.

Setiap pilihan memeriksa semua n kegiatan, jadi biayanya adalah n dikali jumlah jawaban. Jika semua 5000 kegiatan bisa dilakukan satu demi satu, jumlahnya 25 juta pemeriksaan.

Algoritma

Atur count = 0 dan lastFinish = -1, di bawah setiap waktu mulai.
Pindai semua aktivitas untuk mencari aktivitas yang memiliki start[i] > lastFinish dan selesai paling awal.
Jika tidak ada, kembalikan count.
Jika ada, tambahkan 1 ke count, atur lastFinish ke waktu selesai aktivitas tersebut, lalu pindai lagi.

def maxActivities(start, finish):
    n = len(start)
    count = 0
    last_finish = -1  # nothing taken yet; every start is at least 0
    while True:
        # among the activities that start after last_finish, find the one that ends first
        pick = -1
        for i in range(n):
            if start[i] > last_finish and (pick == -1 or finish[i] < finish[pick]):
                pick = i
        if pick == -1:
            return count
        count += 1
        last_finish = finish[pick]

Urutkan berdasarkan waktu selesai, lalu pilih secara rakus

Intuisi

Urutkan berdasarkan waktu selesai sekali, lalu kamu akan menemui aktivitas dalam urutan yang dicari oleh pemindaian di atas. Telusuri daftar yang sudah diurutkan sambil menyimpan lastFinish, yaitu waktu selesai aktivitas terakhir yang kamu pilih. Aktivitas dengan start[i] > lastFinish adalah aktivitas yang selesai paling awal dan masih cocok, jadi pilihlah. Aktivitas lainnya bertabrakan dengan pilihan terakhirmu, jadi melewatkannya tidak akan merugikan.

Setelah diurutkan, contoh pertama berisi 10 hingga 13, 12 hingga 16, 14 hingga 19, 21 hingga 22, 20 hingga 24, 25 hingga 30. Kamu memilih yang pertama, ketiga, keempat, dan keenam: 12 tidak setelah 13, dan 20 tidak setelah 22.

Tidak diperlukan aturan untuk waktu selesai yang sama. Setelah kamu memilih aktivitas yang selesai pada t, setiap aktivitas lain yang selesai pada t dimulai pada atau sebelum t dan dilewatkan.

Algoritma

Urutkan aktivitas berdasarkan finish, pindahkan setiap nilai mulai bersama nilai selesai.
Tetapkan count = 0 dan lastFinish = -1.
Untuk setiap aktivitas dalam urutan tersebut, jika start[i] > lastFinish, tambahkan 1 ke count dan tetapkan lastFinish = finish[i].
Kembalikan count.

def maxActivities(start, finish):
    order = sorted(range(len(start)), key=lambda i: finish[i])  # earliest finish first
    count = 0
    last_finish = -1  # nothing taken yet; every start is at least 0
    for i in order:
        if start[i] > last_finish:
            count += 1
            last_finish = finish[i]
    return count

Jebakan dan kasus tepi

Mengurutkan berdasarkan waktu mulai. Pada contoh ketiga, 0 sampai 100 mulai lebih dulu dan menghalangi tiga aktivitas lainnya.
Memilih aktivitas terpendek terlebih dahulu. Dengan 1 sampai 5, 5 sampai 6, dan 6 sampai 10, aktivitas terpendek adalah 5 sampai 6, yang bertabrakan dengan kedua aktivitas lainnya; 1 sampai 5 dan 6 sampai 10 menghasilkan 2.
Membandingkan dengan ≥ alih-alih >. Pada contoh kedua, hasilnya 3, bukan 2.
Mengurutkan finish sendiri. Setiap waktu mulai harus tetap berpasangan dengan waktu selesai miliknya, atau waktu mulai akan berpasangan dengan aktivitas yang salah.
Memulai lastFinish dari 0. Aktivitas tunggal dari 0 sampai 1 kemudian dilewati, karena 0 > 0 bernilai false.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu masalah pemilihan aktivitas?

Mengurutkan berdasarkan waktu selesai membutuhkan O(n log n), dan proses greedy setelahnya membutuhkan O(n), jadi pengurutanlah yang paling memakan waktu. Jika aktivitas sudah diurutkan berdasarkan waktu selesai, proses itu saja cukup untuk menyelesaikannya dalam waktu O(n) dan ruang tambahan O(1).

Apa itu masalah N pertemuan dalam satu ruangan?

Ini masalah yang sama, kali ini menggunakan rapat: satu ruangan, N rapat, dan sebuah rapat hanya dapat dimulai setelah rapat sebelumnya selesai. Urutkan rapat berdasarkan waktu selesai, lalu pilih setiap rapat yang dimulai setelah rapat terakhir yang dipilih selesai. Untuk mencantumkan rapat, catat setiap indeks yang kamu pilih. Jika waktu selesai sama, dahulukan indeks yang lebih kecil.

Apakah masalah pemilihan aktivitas menggunakan pemrograman dinamis?

Bisa, tetapi tidak harus. Tabel aktivitas yang diurutkan berdasarkan waktu selesai, dengan jumlah aktivitas terbanyak yang berakhir pada setiap aktivitas, memberikan jawabannya dalam O(n²). Pilihan greedy selalu aman, jadi cukup lakukan satu kali penelusuran. Tabel menjadi alat yang tepat ketika aktivitas memiliki nilai dan kamu ingin memaksimalkan totalnya.

def maxActivities(start, finish):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

start = [10, 12, 20, 14, 25, 21]
finish = [13, 16, 24, 19, 30, 22]

Output yang diharapkan