ข้อสอบท้ายค่าย 2 ปีการศึกษา 2566 ศูนย์ สอวน. มหาวิทยาลัยเทคโนโลยีพระจอมเกล้าธนบุรี ข้อ FreeDay

---

Author: njoop

---

Problem

สรุปโจทย์

มีคนอยู่ \(N\) คน โดยแต่ละคน จะไม่ว่างกันเป็นช่วงของวันที่ \(S_{(i, j)}\) ถึง \(E_{(i, j)}\) (ก็คือ ช่วงที่ \(j\) ของคนที่ \(i\) เริ่มที่ \(S_{(i, j)}\) และจบที่ \(E_{(i, j)}\)) โดยคนที่ \(i\) จะมีช่วงที่ไม่ว่างอยู่ \(M_i\) ช่วง

สิ่งที่ต้องทำ

หาช่วงของวันที่คนทุกคนว่างพร้อมกัน (โดยไม่นับช่วงที่ไม่มีขอบเขต)

Warning

คำว่า "ไม่ว่างกันเป็นช่วงของวันที่ \(S_{(i, j)}\) ถึง \(E_{(i, j)}\)" ในโจทย์จะไม่รวมวันที่ \(E_{(i, j)}\) หรืออีกนัยหนึ่งคือ จะไม่ว่างในช่วง \([S_{(i, j)}, E_{(i, j)})\)

Constraints

\(2 \leq N \leq 10^4\)
\(1 \leq S_{(i,1)} < E_{(i, 1)} < S_{(i, 2)} < E_{(i, 2)} < ... \leq 1,000\)
\(M_1 + M_2 + ... + M_N \leq 10^5\)

Prerequisites

• Sweep Line

---

Solution

วิธีทำ

สิ่งที่โจทย์ให้หา คือ ช่วงที่ทุกคนว่างพร้อมกัน หรือ ช่วงที่มีคนไม่ว่าง \(0\) คน สามารถใช้ Sweep Line ในการแก้ปัญหาได้

แนวคิดคร่าวๆ มีดังนี้

สร้างอาร์เรย์ \(P\) ที่มีขนาด \(\geq 1002\) ช่อง (มากกว่าหรือเท่ากับขอบเขตของวันที่โจทย์กำหนด) โดยที่ให้ค่าของทุกช่องเป็น 0

ในช่วงที่ "ไม่ว่าง" ของแต่ละคน นิยามให้สำหรับช่วงที่ \(i\) ให้เวลาเริ่มเป็น \(S_i\) และเวลาจบเป็น \(E_i\) ให้เพิ่มค่าในตำแหน่งที่ \(S_i\) ไป 1 และลดค่าในตำแหน่งที่ \(E_i\) ไป 1

หลังจากพิจารณาทุกช่วงแล้ว ในวันที่ \(j\) จำนวนคนที่ไม่ว่างจะเป็น \(P_1 + P_2 + ... + P_j\) เราสามารถคำนวณว่าในแต่ละวัน มีคนไม่ว่างกี่คนได้ ถ้าเกิดวันไหนมีคนไม่ว่าง \(0\) คน จะถือวันนั้นเป็นวันที่ทุกคนว่าง

ในการหาคำตอบ (ช่วงที่ทุกคนว่างพร้อมกัน) อาจเจอปัญหาคือ บางช่วงเป็นช่วงที่ไม่มีขอบเขต ทำให้คำตอบที่ออกมาผิด สามารภแก้ได้โดยการนำ \(0\) และ \(1001\) มาพิจารณาในการหาช่วง และไม่ต้องแสดงถ้าเกิดว่ามีช่วงใดช่วงหนึ่งเริ่มที่ \(0\) หรือจบที่ \(1001\)

---

Code:

c2_kmutt_66_freeday.cpp

#include <bits/stdc++.h>

using namespace std;

int p[1002], cnt, s, e, n, m, st;
vector<pair<int, int>> ans;

int main() {
    cin.tie(0)->sync_with_stdio(0);

    // input
    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> m;
        while(m--) {
            cin >> s >> e;
            // update p โดย:
            p[s]++; // เพิ่ม "จำนวนคนที่ไม่ว่าง" ใน p
            p[e]--; // ลบ "จำนวนคนที่ว่าง" ออกจาก p
        }
    }

    // การคำนวณ
    for(int i=0; i<=1001; i++) { // 0 และ 1001 เพิ่อการจัดการช่วงที่ไม่มีขอบเขต
        cnt += p[i];
        if(st == 0 && cnt == 0) { // หมายความว่า ตอนนี้ทุกคนว่าง ก็จะตั้ง s เป็นตำแหน่งเริ่มต้น
            s = i;
            st = 1;
        } else if(st == 1 && cnt != 0) { // หมายความว่า ระยะวันที่ว่างได้จบลง (cnt != 0) ก็จะตั้ง e เป็นจุดสิ้นสุด
            e = i;
            st = 0;
            ans.push_back({s, e});
        }
    }
    int sz = 0;

    // output
    for(int i=0; i<ans.size(); i++) {
        if(ans[i].first == 0 || ans[i].second == 1001) continue; // หากเป็นช่วงไร้ขอบเขต ก็ไม่ต้อง output ออกมา
        cout << ans[i].first << " " << ans[i].second << " ";
        sz++; 
    }

    // ถ้าไม่มีช่วงวันที่ว่างเลย พิมพ์ -1
    if(sz == 0) cout << -1;
    return 0;
}

Total Time Complexity

\(O(N + M)\) เมื่อ M = \(\sum M_i\)