Temu duga pengekodan: Bagaimanakah anda memaksimumkan ganjaran dengan kerja yang tidak bertindih?

Prompt dan kes penggunaan

Setiap kerja ialah (start, end, reward). Pilih kerja serasi dengan jumlah ganjaran maksimum; masa tamat yang sama dengan permulaan seterusnya dibenarkan. Untuk (1,3,50), (3,5,40), (2,6,100), dua kerja pertama menang dengan ganjaran 90. Ini ialah soalan coding yang menguji susunan selang, carian pendahulu (predecessor lookup) dan pengaturcaraan dinamik, tanpa mengira bahasa pelaksanaan.

Bahan algoritma awam menggunakan penjadualan selang/kerja berwajaran sebagai latihan pengaturcaraan dinamik dan corak selang, dan akaun temu duga awam juga merekodkan varian penjadualan selang. Nyatakan keperluan yang boleh disahkan tanpa mendakwa kekerapan temu duga yang tidak boleh disahkan.

Perkara yang dinilai oleh penemu duga

• Sama ada anda mengisih mengikut masa tamat supaya kerja terakhir yang dipilih membentuk keputusan yang teratur.
• Sama ada anda mentakrifkan p(i), iaitu kerja terakhir yang tamat tidak lewat daripada masa kerja i bermula.
• Sama ada anda membandingkan melangkau dan mengambil kerja semasa dan bukannya secara tamak (greedy) mengambil ganjaran individu terbesar.
• Sama ada carian binari mengurangkan carian pendahulu kepada O(log n) dan sama ada anda boleh membina semula kerja yang dipilih.
• Sama ada anda mengendalikan end == start, masa tamat yang sama, input kosong dan ganjaran sifar.

Penjelasan sebelum menjawab

• Adakah masa tamat dan masa mula yang sama dianggap serasi? Jawapan ini menganggap ya: end <= start.
• Bolehkah ganjaran bernilai negatif? Jika ya, benarkan secara eksplisit untuk tidak memilih sebarang kerja, dengan garis dasar 0.
• Adakah hanya ganjaran maksimum yang diperlukan? Artikel ini juga membina semula set kerja; tinggalkan data induk jika tidak diperlukan.
• Adakah masa berbentuk integer? Pengisihan hanya memerlukan kebolehbandingan; carian binari tidak memerlukan integer berturutan.
• Bolehkah sesuatu kerja dipilih dua kali? Anggap setiap kerja input boleh dipilih paling banyak sekali.
• Bolehkah start > end berlaku? Tolak atau normalkan sebelum pengulangan; jangan sembunyikan data yang tidak sah.
• Bagaimanakah selang yang sama harus disusun? Gunakan pemutus seri (tie-break) yang stabil; sebarang ganjaran optimum boleh diterima.

Rangka kerja jawapan 30 saat

"Saya mengisih kerja mengikut end dan membiarkan dp[i] menjadi ganjaran terbaik daripada i kerja pertama. Bagi kerja i, lakukan carian binari untuk kerja terakhir yang tamat selewat-lewatnya pada start[i]; sebut saiz awalan serasinya sebagai p. Hubungan pengulangannya ialah dp[i] = max(dp[i-1], reward[i] + dp[p]): langkau kerja itu atau ambil bersama awalan serasinya. Saya menyimpan penanda pilihan dan menjejak ke belakang (backtrack) untuk memulihkan kerja. Pengisihan dan setiap carian binari menghasilkan masa O(n log n) dan tatasusunan menggunakan ruang O(n)."

Jawapan mendalam langkah demi langkah

Langkah 1: Terangkan mengapa peraturan tamak (greedy) tidak mencukupi.

Tamak masa-tamat-terawal (earliest-finish-time greedy) adalah betul apabila setiap kerja mempunyai nilai yang sama. Dengan ganjaran yang berbeza, kerja singkat bernilai rendah boleh menghalang gabungan yang lebih baik, jadi masa tamat tempatan atau ganjaran tempatan sahaja tidak mencukupi.

Langkah 2: Takrifkan keadaan teratur.

Selepas pengisihan, biarkan dp[i] menjadi optimum untuk kerja 0..i-1, dengan dp[0] = 0. Melangkau kerja i-1 serta-merta memberikan dp[i-1].

Langkah 3: Kira pendahulu.

Bagi kerja i-1, cari j < i-1 terbesar dengan end[j] <= start[i-1]. Lakukan carian binari pada masa tamat yang diisih dan kembalikan saiz awalan serasinya p; mengambil kerja tersebut menghasilkan reward[i-1] + dp[p].

Langkah 4: Tulis hubungan pengulangan dan pembinaan semula.

dp[0] = 0
for i = 1..n:
  skip = dp[i - 1]
  take = reward[i - 1] + dp[p(i - 1)]
  dp[i] = max(skip, take)
  chose[i] = take > skip

Jejak ke belakang dari i = n: jika chose[i] adalah benar, rekod kerja i-1 dan lompat ke p(i-1); jika tidak, kurangkan i. Songsangkan senarai yang dikumpul. Tetapkan pemutus seri apabila kedua-dua ganjaran adalah sama.

Langkah 5: Buktikan ketepatan.

Sebarang optimum ke atas i kerja pertama sama ada mengecualikan kerja i-1, menghasilkan paling banyak dp[i-1], atau memasukkannya. Dalam kes kedua, setiap kerja lain terletak dalam p(i-1) kerja serasi yang pertama, menghasilkan paling banyak reward[i-1] + dp[p(i-1)]. Pengulangan mengambil nilai yang lebih besar daripada kes-kes menyeluruh ini. Dengan kes asas dp[0] = 0, aruhan membuktikan setiap keadaan adalah optimum.

Langkah 6: Lindungi sempadan pelaksanaan.

Carian pendahulu mesti menggunakan <= supaya kerja bersebelahan kekal serasi. Mulakan dari sifar untuk menyokong ganjaran negatif dan set kosong. Songsangkan hasil penjejakan ke belakang kerana pembinaan semula berjalan dari hujung.

Langkah 7: Analisis kerumitan.

Pengisihan mengambil kos O(n log n), dan satu carian binari bagi setiap kerja juga mengambil kos O(n log n) secara keseluruhan. Tatasusunan pengaturcaraan dinamik, pendahulu dan pilihan menggunakan ruang O(n). Nyatakan saiz output secara berasingan jika ia dikira.

Langkah 8: Kenal pasti alternatif.

Jika masa tamat ialah integer kecil yang terikat, imbasan berindeks masa boleh mengelakkan pengisihan perbandingan. Jika ganjaran adalah sama, kaedah tamak tamat-terawal adalah mencukupi. Had paling banyak k kerja atau berbilang sumber menambah dimensi keadaan dan memerlukan hubungan pengulangan baharu.

Contoh jawapan berkualiti tinggi

"Saya mengisih mengikut masa tamat dan mentakrifkan dp[i] sebagai ganjaran maksimum antara i kerja pertama. Bagi setiap kerja, lakukan carian binari untuk pendahulu terakhir dengan end <= start. Melangkau memberikan dp[i-1]; mengambil memberikan reward[i] + dp[p(i)], jadi saya mengekalkan nilai yang lebih besar dan merekodkan pilihan untuk penjejakan ke belakang. Bukti membahagikan setiap optimum mengikut sama ada ia mengandungi kerja semasa; jika ya, baki kerja mesti datang daripada awalan yang serasi. Pengisihan dan carian binari menghasilkan masa O(n log n) dan ruang bantuan O(n). Saya menguji kerja bersebelahan, masa tamat yang sama, ganjaran negatif, pertindihan lengkap dan input kosong."

Kesilapan biasa

• Tamak mengikut ganjaran terbesar → satu kerja boleh menghalang gabungan jumlah yang lebih tinggi → bandingkan ambil dan langkau dengan DP.
• Menganggap tamat/mula yang sama sebagai konflik → kerja bersebelahan yang sah hilang → gunakan end <= start.
• Hanya mengisih mengikut mula → dp[i-1] tidak lagi menerangkan awalan yang stabil → isih mengikut tamat.
• Imbasan pendahulu secara linear → jumlah masa menjadi O(n²) → lakukan carian binari pada masa tamat.
• Memulakan dari ganjaran pertama → input serba negatif tidak boleh memilih set kosong → tetapkan dp[0] = 0.
• Terlupa untuk menyongsangkan penjejakan ke belakang → kerja yang dipilih dikembalikan secara terbalik → songsangkan selepas pengumpulan.
• Membiarkan seri ganjaran sama tanpa dinyatakan → output berubah antara larian berbeza → tetapkan pemutus seri.
• Mendakwa satu dimensi mengendalikan had sumber → kekangan tambahan tidak diwakili → tambah dimensi atau modelkan semula.

Soalan susulan dan respons

Soalan susulan 1: Mengapakah peraturan sempadan sama selamat?

Jika satu kerja tamat tepat pada masa kerja lain bermula, ia tidak bertindih di bawah konvensyen yang dinyatakan. Oleh itu, ujian pendahulu mesti menyertakan kesaksamaan; menukarnya kepada < akan menyelesaikan masalah yang berbeza.

Soalan susulan 2: Bolehkah ini sentiasa menjadi O(n)?

Dengan masa integer kecil yang terikat, pengimbasan masa langsung boleh menjadi linear. Dalam model perbandingan umum, pengisihan itu sendiri mengambil kos O(n log n), jadi jangan menjanjikan masa linear tanpa syarat.

Soalan susulan 3: Bagaimanakah anda membina semula kerja?

Simpan bit pilihan atau penunjuk induk. Dari i = n, ambil kerja semasa dan lompat ke pendahulunya, atau kurangkan indeks semasa melangkau; songsangkan kerja yang dikumpul.

Soalan susulan 4: Bagaimana jika paling banyak k kerja boleh dipilih?

Tambah dimensi kiraan seperti dp[i][c] untuk ganjaran terbaik menggunakan c kerja antara i yang pertama. Masa dan ruang meningkat sewajarnya.

Soalan susulan 5: Bagaimana jika ganjaran bergantung pada kerja bersebelahan?

Andaian ganjaran bebas tidak lagi terpakai. Sertakan hubungan bersebelahan dalam keadaan atau modelkannya sebagai kos peralihan; hubungan pengulangan asal tidak berasas tanpa perubahan itu.

Soalan susulan 6: Bagaimana jika semua kerja mempunyai masa tamat yang sama?

Pengisihan stabil sudah memadai. Pendahulu mereka biasanya sama, dan hubungan pengulangan masih membandingkan setiap calon. Untuk selang yang sama, hanya ganjaran terbaik yang penting.

Soalan susulan 7: Bilakah pendekatan tamak adalah betul?

Apabila semua ganjaran adalah sama dan matlamatnya adalah untuk memilih bilangan kerja terbanyak, pendekatan tamak masa-tamat-terawal mempunyai hujah pertukaran (exchange argument). Dengan ganjaran yang tidak sama, gunakan pengaturcaraan dinamik berwajaran.