Maximum Number of Events That Can Be Attended ใน C++ : หา Event สูงสุดที่เข้าร่วมได้

ให้ Array events[i] = [startDay, endDay] สามารถเข้าร่วม Event i ได้ที่วัน d ใดก็ได้ที่ startDay ≤ d ≤ endDay แต่ **1 วันเข้าร่วมได้สูงสุด 1 Event** หา **จำนวน Event สูงสุด** ที่เข้าร่วมได้

ตัวอย่าง

events = [[1,4], [4,4], [2,2], [3,4], [1,1]]
Optimal Schedule:
Day 1: Event [1,1] (Index 4)
Day 2: Event [2,2] (Index 2)
Day 3: Event [3,4] (Index 3)
Day 4: Event [4,4] (Index 1)
Total: 4 Events
Output: 4

แนวทาง: Greedy + Priority Queue (Min-Heap on End Day)

1. Sort Events ตาม startDay 昇序
2. Iterate วัน d = 1 .. MaxDay (หรือจน Events หมด):
   • Push **End Day** ของ Events ที่ startDay == d เข้า **Min-Heap
   • Pop Heap จน top >= d (ลบ Events ที่หมดอายุก่อนวันนี้)
   • ถ้า Heap ไม่ว่าง -> **Attend Event ที่จบเร็วที่สุด (Min End Day)**: Pop Heap, ans++

Greedy Choice: วันนี้เลือก Event ที่ **จบเร็วที่สุด** (Earliest Deadline) เพื่อทิ้งวันว่างให้ Event อื่นมากที่สุด

ตัวอย่างโค้ด C++

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

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0]; // Sort by startDay
    }

    int maxEvents(vector<vector<int>>& events) {
        sort(events.begin(), events.end(), cmp);
        int n = events.size();
        int ans = 0, i = 0;

        // Min-Heap of endDays
        priority_queue<int, vector<int>, greater<int>> pq;

        for (int day = 1; day <= 100000; day++) { // Max constraint
            // Add events starting today
            while (i < n && events[i][0] == day) {
                pq.push(events[i][1]);
                i++;
            }
            // Remove expired events
            while (!pq.empty() && pq.top() < day) pq.pop();

            // Attend one event (earliest ending)
            if (!pq.empty()) {
                pq.pop();
                ans++;
            }
            // Early exit: no more events to start and heap empty
            if (i == n && pq.empty()) break;
        }
        return ans;
    }
};

Input / Output

Input:  [[1,4],[4,4],[2,2],[3,4],[1,1]]
Output: 4

ความซับซ้อน (Complexity)

• Time: O(N log N + D log N) — Sort + Heap Ops (D = Max Day ~ 1e5)
• Space: O(N) — Heap + Sorted Events

จุดสำคัญ

• Sort by Start Day
• Min-Heap on End Day (Earliest Deadline First)
• Process Day by Day (Sweep Line)

Classic Interval Scheduling Maximization Problem ครับ