【題解】CSES - Movie Festival

題目連結

題目大意

給定 $n$ 個電影開始和結束的時間 $a_i$ 和 $b_i$，問最多可以看幾部電影？

• $1 \leq n \leq 2 \cdot 10^5$
• $1 \leq a < b \leq 10^9$

題解

考慮 greedy，每次都選擇看不重疊且最早結束的電影，因此我們對結束的時間 $b_i$ 進行排序後直接模擬即可。其他的實作細節請參考 code。

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<pair<int, int>> a(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i].first >> a[i].second;
	}
	sort(a.begin(), a.end(), [](pair<int, int> a, pair<int, int> b) {
		return a.second < b.second;
	});
	int ans = 0;
	int end = 0;
	for(auto [x, y] : a) {
		if(x >= end) {
			ans++;
			end = y;
		}
	}
	cout << ans << "\n";
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】CSES - Movie Festival