Хамгийн эрт дуусдагийг нь түрүүлж сонгосоор, хоорондоо давхцахгүй хамгийн олон ажлыг сонгодог Greedy арга.

IntermediateХугацаа: O(n log n)Санах ой: O(n)

Эхлээд жижиг бодлого

Дугуйлангууд: 1–3, 2–5, 4–6, 6–8, 5–9. Дуусах цагаар эрэмбэлбэл яг ийм дараалалтай.

1–3-ыг сонгоно (last = 3). 2–5 нь 3-аас өмнө эхэлдэг тул алгасна. 4–6-г сонгоно (last = 6). 6–8 яг 6-д эхэлдэг тул сонгоно (last = 8). 5–9-ийг алгасна. Хариу 3.

Энгийн аргаас санаа руу

Энгийн арга бол бүх дэд олонлогийг шалгах: 2ⁿ хувилбар, n = 30 бол тэрбум. Хэтэрхий удаан.

Greedy санаа: хамгийн эрт дуусдагийг нь сонго. Ингэвэл үлдсэн цаг хамгийн их байна. Дараа нь түүнтэй давхцахгүй, хамгийн эрт дуусдагийг сонгоно гэх мэт. Эхлэх цаг эсвэл үргэлжлэх хугацаагаар нь сонгох нь буруу хариу өгдөг.

Нэр томьёо ба тэмдэглэгээ

a[i] = {e, s}
Ажлыг дуусах цагийг нь эхэнд тавьж хадгална. sort шууд дуусах цагаар эрэмбэлнэ.
last
Сүүлд сонгосон ажлын дуусах цаг. Эхэндээ 0.
cnt
Сонгосон ажлын тоо.
Greedy
Алхам бүрт тухайн үедээ хамгийн сайн сонголтыг хийж, буцаж засдаггүй арга.
цаг0123456789101–4
3–5
0–6
5–7
3–9
5–9
6–10
8–11

Нэг өдөр 8 дугуйлан хичээллэнэ. Хоёр газар зэрэг байж болохгүй. Хамгийн олондоо хэдэд нь явж чадах вэ?

Алхам 1 / 14
Хурд
  • Шалгаж буй
  • Сонгосон
  • Давхцсан тул алгассан
Слайд 1 / 6

Аль болох олон дугуйлан

Нэг өдөр олон дугуйлан хичээллэнэ, гэхдээ хоёр газар зэрэг байж болохгүй. Хамгийн олондоо хэдэд нь явж чадах вэ? Мөр бүр нэг дугуйлан, нүд бүр нэг цаг.

activity-selection.cpp
#include <bits/stdc++.h>
using namespace std;
int n;
pair<int, int> a[100005];
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int s, e;
cin >> s >> e;
a[i] = {e, s};
}
sort(a, a + n);
int cnt = 0, last = 0;
for (int i = 0; i < n; i++) {
if (a[i].second >= last) {
cnt++;
last = a[i].first;
}
}
cout << cnt << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

Эхлэх, дуусах цагтай олон ажлаас хоорондоо давхцахгүй хамгийн олныг нь сонгоно. Greedy-гийн хамгийн сонгодог жишээ.

Яаж ажилладаг вэ?

1. Ажлуудыг дуусах цагаар нь эрэмбэлнэ. Хосыг {дуусах, эхлэх} гэж хадгалбал sort шууд ингэж эрэмбэлнэ. 2. last нь сүүлд сонгосон ажлын дуусах цаг, эхэндээ 0. 3. Ажил бүрийг дарааллаар нь шалгана. Эхлэх цаг нь last-аас бага биш бол сонгоод, last-ыг түүний дуусах цагаар солино. 4. Бага бол өмнө сонгосонтойгоо давхцаж байгаа тул алгасна. Оролт: эхний мөрөнд n, дараагийн n мөрөнд ажил бүрийн эхлэх ба дуусах цаг.

Яагаад зөв, хэр хурдан бэ?

Хамгийн эрт дуусдаг ажлыг x гэе. Дурын оновчтой хариуны эхний ажлыг x-ээр сольж болно: x түүнээс эрт эсвэл зэрэг дуусдаг тул дараагийн ажлуудтай давхцахгүй. Тиймээс x-ийг сонгосон оновчтой хариу байдаг. Үлдсэн ажлуудад ижил санааг давтана.

Эрэмбэлэх O(n log n), дараагийн loop O(n). n = 100 000 бол 2 сая орчим үйлдэл.

Түгээмэл алдаа

  • Эхлэх цагаар эрэмбэлэх. 0–10, 1–2, 3–4 дээр 0–10-ыг сонгоод 1 гэж хариулна, зөв нь 2.
  • Хамгийн богиноор эрэмбэлэх. 1–5, 4–7, 6–10 дээр 4–7-г сонгоод 1 гэж хариулна, зөв нь 2.
  • >=-ийн оронд > бичих. Тэгвэл 4–6 ба 6–8 шиг шүргэлцсэн ажлуудыг давхцсан гэж үзнэ. Бодлогын нөхцөлийг сайн унш.
  • Pair-ийг {s, e} гэж хадгалах. Тэгвэл sort эхлэх цагаар эрэмбэлнэ.

Хязгаарын тохиолдол

  • n = 1: ганц ажлыг сонгоод хариу 1.
  • Бүгд давхцдаг: хамгийн эрт дуусдаг нэгийг л сонгоно, хариу 1.
  • Огт давхцахгүй: бүгдийг сонгоно, хариу n.
  • Дуусах цаг ижил хоёр ажил: аль нэгийг нь л сонгоно, хариу өөрчлөгдөхгүй.

Өөрийгөө шалга

  1. 2–7, 4–6, 3–9, 1–5 дээр хариу хэд вэ?

    Хариу харах

    1. 1–5-ыг сонгосны дараа бусад нь бүгд 5-аас өмнө эхэлдэг. Эдгээр нь бүгд хоорондоо давхцдаг.

  2. Яагаад last эхэндээ 0 байдаг вэ?

    Хариу харах

    Цаг 0-ээс эхэлдэг тул эхний ажил үргэлж сонгогдоно.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.2–4, 1–3, 3–6, 5–7, 6–9 дээр алгоритмыг гараар ажиллуул.

    Hint харах

    Эхлээд дуусах цагаар эрэмбэл: 1–3, 2–4, 3–6, 5–7, 6–9.

    Хариу ба тайлбар

    1–3 (last = 3), 3–6 (last = 6), 6–9 (last = 9). Хариу 3.

  2. 2.Хариунаас гадна сонгосон ажлуудыг хэвлэдэг болго.

    Hint харах

    Сонгох бүрт хос бүрийн аль хэсгийг хэвлэх вэ?

    Хариу ба тайлбар

    cnt++-ийн дараа cout << a[i].second << " " << a[i].first << "\n"; гэж эхлэх, дуусах цагийг хэвлэнэ.

  3. 3.Үлдсэн ажлууд давхцахгүй болохын тулд хамгийн цөөндөө хэдэн ажлыг хасах вэ?

    Hint харах

    Хамгийн олон давхцахгүй ажлыг үлдээвэл хасах нь хамгийн цөөн.

    Хариу ба тайлбар

    n - cnt. Жишээ нь 2–7, 4–6, 3–9, 1–5, 5–8 дээр 1–5 ба 5–8-ыг үлдээж болох тул 5 − 2 = 3.

Жишээ

Оролт

8
1 4
3 5
0 6
5 7
3 9
5 9
6 10
8 11

Гаралт

3