23.2 เลือกกิจกรรมที่ไม่ซ้อนกัน

หอประชุมของโรงเรียนมีห้องเดียว แต่มีชมรมขอจองหลายรายการ แต่ละรายการบอกเวลาเริ่มกับเวลาจบ สองรายการที่เวลาทับกันใช้ห้องพร้อมกันไม่ได้ ส่วนรายการที่จบ 10 โมงพอดีกับรายการที่เริ่ม 10 โมงพอดีใช้ต่อกันได้ ครูอยากอนุมัติให้ได้ จำนวนรายการมากที่สุด โจทย์นี้เรียกว่า activity selection เป็นโจทย์ greedy ที่เจอบ่อยที่สุด และโจทย์ในค่ายหลายข้อแปลงกลับมาเป็นโจทย์นี้ได้ หน้านี้ลองกฎการเลือกสามแบบ หาว่าแบบไหนถูก แล้วพิสูจน์ด้วยการแลกเปลี่ยน

กฎที่ฟังดูดีสามแบบ

ทุกกฎทำเหมือนกัน คือเรียงรายการตามค่าบางอย่าง แล้วไล่ไปทีละรายการ รับรายการไหนที่ไม่ทับกับที่รับไว้แล้ว ต่างกันแค่ค่าที่ใช้เรียง

กฎแรกพังเมื่อรายการที่เริ่มเช้าสุดยาวมาก กฎที่สองพังเมื่อรายการสั้นอยู่คร่อมรอยต่อของสองรายการ ทั้งสองกฎดูตัวอย่างในโจทย์แล้วอาจได้คำตอบถูกด้วยซ้ำ เพราะตัวอย่างไม่ได้ตั้งใจดัก สิ่งที่สำคัญจริงคือ ห้องว่างเมื่อไร ไม่ใช่รายการเริ่มเมื่อไรหรือยาวแค่ไหน

เลือกรายการที่จบเร็วที่สุด

เรียงตามเวลาจบ แล้วไล่ไป รับรายการที่เริ่มไม่ก่อนเวลาจบของรายการล่าสุดที่รับไว้ ตัวอย่างนี้ใช้เวลาเป็นชั่วโมง เช่น 9 10 คือ 9 โมงถึง 10 โมง

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> events(n);
    for (int i = 0; i < n; i++) {
        int start, finish;
        cin >> start >> finish;
        events[i] = {finish, start}; // (1)!
    }
    sort(events.begin(), events.end());
    int count = 0;
    int last_finish = INT_MIN; // (2)!
    for (int i = 0; i < n; i++) {
        int finish = events[i].first;
        int start = events[i].second;
        if (start >= last_finish) { // (3)!
            cout << "take " << start << "-" << finish << '\n';
            count++;
            last_finish = finish;
        }
    }
    cout << "count = " << count << '\n';
    return 0;
}

1. เก็บเวลาจบไว้เป็น first เพราะ sort ของ pair เรียงตาม first ก่อนตามหน้า 16.4 ได้การเรียงตามเวลาจบโดยไม่ต้องเขียน lambda
2. ยังไม่ได้รับรายการไหน ให้ค่าเริ่มต้นน้อยกว่าทุกเวลา รายการแรกจึงผ่านเงื่อนไขเสมอ INT_MIN คือค่าน้อยสุดของ int
3. ใช้ >= เพราะโจทย์ให้เริ่มตอนที่รายการก่อนจบพอดีได้ ถ้าโจทย์ห้าม ต้องเปลี่ยนเป็น >

8
8 12
9 10
10 11
11 13
12 14
13 15
14 16
15 17

take 9-10
take 10-11
take 11-13
take 13-15
take 15-17
count = 5

เรียงแล้วรายการแรกคือ 9-10 รับไว้ ต่อไป 10-11 เริ่มตอนที่ 9-10 จบพอดี รับได้ รายการ 8-12 จบเป็นลำดับที่สามแต่เริ่ม 8 โมง ทับแล้ว ข้ามไป ไล่จนครบได้ 5 รายการ เรียงใช้เวลา O(N log N) ไล่อีก O(N) รวมเป็น O(N log N)

พิสูจน์ด้วยการแลกเปลี่ยน

ต้องแสดงว่าไม่มีวิธีเลือกไหนได้มากกว่า greedy เริ่มจากรายการแรกที่ greedy รับ เรียกว่า g ซึ่งเป็นรายการที่จบเร็วที่สุดในทั้งหมด ลองหยิบคำตอบที่ดีที่สุดมาสักแบบ ไม่ต้องรู้ว่าเป็นแบบไหน เรียงรายการในคำตอบนั้นตามเวลา ให้ o เป็นรายการแรกของมัน

1. g จบเร็วที่สุดในทุกรายการ จึงจบไม่ช้ากว่า o
2. รายการที่เหลือในคำตอบที่ดีที่สุดทุกรายการเริ่มไม่ก่อนเวลาที่ o จบ จึงเริ่มไม่ก่อนเวลาที่ g จบด้วย
3. เอา o ออก ใส่ g แทน ไม่มีอะไรทับกัน จำนวนรายการเท่าเดิม ได้คำตอบที่ดีที่สุดอีกแบบหนึ่งที่ขึ้นต้นด้วย g
4. ตัดรายการที่ทับกับ g ทิ้งทั้งหมด ที่เหลือคือโจทย์เดิมที่เล็กลง และ greedy ก็เลือกรายการที่จบเร็วที่สุดในส่วนที่เหลือ ใช้เหตุผลข้อ 1 ถึง 3 ซ้ำได้ทุกขั้น

ทุกขั้น greedy เลือกเหมือนคำตอบที่ดีที่สุดแบบใดแบบหนึ่งได้เสมอ จำนวนที่ greedy ได้จึงเท่ากับจำนวนที่ดีที่สุด ลองใช้เหตุผลเดียวกันกับกฎ "เริ่มเร็วที่สุด" จะติดที่ข้อ 1 เพราะรายการที่เริ่มเร็วที่สุดอาจจบช้ากว่า o มาก แลกแล้วไปทับรายการถัดไป ตรงกับตัวอย่างที่พังในตาราง

เทียบกับการลองทุกแบบ

วิธีที่ถูกแน่ๆ คือลองทุกเซตของรายการแบบบทที่ 21 แต่ละรายการเลือกว่าไม่รับ หรือรับถ้ายังไม่ทับกับที่รับไว้ แล้วจำจำนวนที่มากที่สุด สองรายการทับกันเมื่อแต่ละรายการเริ่มก่อนอีกรายการจบ

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> start_time, finish_time;
vector<int> chosen;
int best = 0;

bool fits(int k)
{
    for (int j : chosen) {
        if (start_time[k] < finish_time[j] && start_time[j] < finish_time[k]) {
            return false;
        }
    }
    return true;
}

void try_events(int k)
{
    if (k == n) {
        best = max(best, (int)chosen.size());
        return;
    }
    try_events(k + 1);
    if (fits(k)) {
        chosen.push_back(k);
        try_events(k + 1);
        chosen.pop_back();
    }
}

int main()
{
    cin >> n;
    start_time.resize(n);
    finish_time.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> start_time[i] >> finish_time[i];
    }
    try_events(0);
    cout << "best = " << best << '\n';
    return 0;
}

8
8 12
9 10
10 11
11 13
12 14
13 15
14 16
15 17

best = 5

ได้ 5 เท่ากับ greedy ป้อนตัวอย่างของกฎ "สั้นที่สุดก่อน" ในตารางข้างบน ได้ best = 2 ยืนยันว่ากฎนั้นผิด แต่วิธีนี้ลองได้ถึง 2^N แบบ วัดบนเครื่องเดียวกับหน้า 23.1 รายการสุ่มเวลาเริ่ม 0 ถึง 1000 ยาว 1 ถึง 100 รันแต่ละแบบ 5 รอบ

การลองทุกเซตเร็วกว่า 2^N มาก เพราะรายการที่ทับกันถูกตัดทิ้งตั้งแต่ต้น แต่ก็ยังโตเร็วจนใช้ไม่ได้ตั้งแต่ราว N = 50 ส่วน greedy กับรายการหนึ่งล้านรายการ เวลาเกือบทั้งหมดคือการอ่านข้อมูลกับการเรียง โปรแกรม greedy ที่วัดตัดบรรทัดพิมพ์ take ออกและเปิดการอ่านเขียนแบบเร็วตามหน้า 15.3

ลองทำให้พัง

แบบที่ 1 เก็บ pair ผิดลำดับ

เก็บเป็น {start, finish} ตามลำดับที่อ่านเข้ามา ซึ่งดูเป็นธรรมชาติกว่า

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> events(n);
    for (int i = 0; i < n; i++) {
        cin >> events[i].first >> events[i].second;
    }
    sort(events.begin(), events.end());
    int count = 0;
    int last_finish = INT_MIN;
    for (int i = 0; i < n; i++) {
        int start = events[i].first;
        int finish = events[i].second;
        if (start >= last_finish) {
            cout << "take " << start << "-" << finish << '\n';
            count++;
            last_finish = finish;
        }
    }
    cout << "count = " << count << '\n';
    return 0;
}

8
8 12
9 10
10 11
11 13
12 14
13 15
14 16
15 17

take 8-12
take 12-14
take 14-16
count = 3

คอมไพล์ผ่าน รันได้ ไม่มีอะไรเตือน แต่ sort เรียงตาม first ซึ่งตอนนี้คือเวลาเริ่ม โปรแกรมจึงกลายเป็นกฎ "เริ่มเร็วที่สุดก่อน" รับ 8-12 ที่ยาวสี่ชั่วโมงไปก่อน ได้แค่ 3 รายการ เวลาเรียง pair ให้ถามตัวเองทุกครั้งว่าค่าไหนต้องเป็นตัวหลักในการเรียง แล้ววางไว้เป็น first

แบบที่ 2 ใช้ > แทน >=

ในโปรแกรม activity เปลี่ยนเงื่อนไขเป็น if (start > last_finish) แล้วป้อนข้อมูลเข้าชุดเดิม

take 9-10
take 11-13
take 14-16
count = 3

เหลือ 3 รายการแทน 5 รายการ 10-11 เริ่มตอน 9-10 จบพอดีจึงถูกข้าม 13-15 ก็ถูกข้ามด้วยเหตุผลเดียวกัน แล้ว 14-16 ที่รับแทนยังไปทับ 15-17 อีก โจทย์แต่ละข้อนิยามเรื่องเวลาชนกันพอดีไม่เหมือนกัน บางข้อให้ต่อกันได้ บางข้อต้องห่างอย่างน้อยหนึ่งหน่วย อ่านโจทย์ให้ชัดแล้วทดสอบด้วยรายการที่จบกับเริ่มตรงกันพอดีทุกครั้ง

สรุป

• เลือกกิจกรรมให้ได้มากที่สุด เรียงตามเวลาจบ รับรายการที่เริ่มไม่ก่อนรายการล่าสุดจบ ใช้เวลา O(N log N)
• กฎเริ่มเร็วสุดและสั้นสุดฟังดูดีแต่ผิด มีตัวอย่างสามรายการที่ทำให้พังได้
• พิสูจน์แบบแลกเปลี่ยน รายการแรกของคำตอบที่ดีที่สุดแลกเป็นรายการที่จบเร็วที่สุดได้เสมอโดยจำนวนไม่ลด
• เก็บค่าที่ใช้เรียงไว้เป็น first ของ pair และระวัง > กับ >= ตรงเวลาที่ชนกันพอดี