Танд N ширхэг төсөл (project) өгөгдөнө. Төсөл бүр дараах мэдээлэлтэй:

• эхлэх хугацаа start[i]
• дуусах хугацаа end[i]
• ашиг value[i]

Та эдгээр төслүүдээс заримыг нь сонгож болно.

⚠️ Гол нөхцөл

Хэрвээ та хоёр төслийг хоёуланг нь сонговол:

? тэдгээрийн хугацаа давхцах ёсгүй

Өөрөөр хэлбэл:

• end[i] ≤ start[j] (эсвэл эсрэгээр)

? Нэмэлт нөхцөл (илүү сонирхолтой болгох)

Та хамгийн ихдээ K ширхэг төсөл сонгож болно.

? Зорилго

• ? Давхцахгүй, хамгийн ихдээ K төсөл сонгон
• ? Нийт ашгийг хамгийн их болго

Оролт:

N K
s1 e1 v1
s2 e2 v2
...
sN eN vN

• N — төслийн тоо
• K — хамгийн их сонгож болох төслийн тоо
• si — эхлэх хугацаа
• ei — дуусах хугацаа
• vi — ашиг

Гаралт:

хамгийн их боломжит ашиг

Хязгаарлалтууд:

• \(1 ≤ N ≤ 2 × 10⁵\)
• \(1 ≤ K ≤ 200\)
• \(0 ≤ si < ei ≤ 10⁹\)
• \(1 ≤ vi ≤ 10⁹\)

Дэд бодлого

Жишээ:

Оролт-1

4 2
1 3 5
2 5 6
4 6 5
6 7 4

Гаралт-1

10

Тайлбар-1

Төслүүд:

№   start   end value
1   1   3   5
2   2   5   6
3   4   6   5
4   6   7   4

Боломжит сонголтууд:

1 + 3 → 5 + 5 = 10 ✅

2 + 4 → 6 + 4 = 10 ✅

1 + 4 → 5 + 4 = 9

? Хамгийн их: 10

Оролт-2

3 1
1 10 5
2 3 3
4 5 4

Гаралт-2

5

Тайлбар-2

K = 1 тул зөвхөн 1 төсөл сонгоно

? Хамгийн их ашигтай нь: (1,10) → 5