題意#
題目給定影展期間有 \( n \) 部電影，並已知每部電影的「開始時間」與「結束時間」。
同一時間內只能觀看一部電影。
我們需要求出最多能「完整」看完幾部電影。
思路#
此為時間排程中經典的貪婪問題，又稱「活動選擇問題（Activity Selection Problem）」。
最佳的貪婪策略為：「優先選擇最早『結束』的電影」。
因為電影越早結束，保留給後續活動的空檔就越多，自然能最大化觀看的總數量。
在實作上，將所有電影依照「結束時間」從小到大排序。
接著依序掃描陣列，若某部電影的開始時間晚於或等於「上一部看過電影的結束時間」，表示時間不衝突。此時我們便選擇觀看該部電影，並更新對應的結束時間。
依此策略遍歷陣列計算出的數量，即為最多能觀看的電影數。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
int n; cin >> n;
// 儲存每部電影的 {結束時間, 開始時間}，特地反過來存以便直接利用 fi 排序
vector<pair<int, int>> v(n);
for (auto &i : v) cin >> i.se >> i.fi;
// 按照「結束時間」從小到大排序
sort(all(v));
// last 記錄上一部看完電影的結束時間
int last = 0, cnt = 0;
// 依序掃描所有電影
for (auto &i : v)
// 如果這部電影的開始時間 >= 上一部的結束時間，代表可以看
if (last <= i.se) cnt++, last = i.fi;
// 輸出最多能看幾部電影
cout << cnt;
}
