AcWing 3818. 餐厅
原题链接
简单
作者:
origami
,
2021-08-27 21:25:09
,
所有人可见
,
阅读 283
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int, int> ii;
const int N = 1e6;
ii q[N];
bool cmp(ii& a, ii& b) {
if (a.first == b.first)
return a.second < b.second;
return a.first < b.first;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++)
// left --> first right --> second
cin >> q[i].first >> q[i].second;
// 排序
sort(q, q + n, cmp);
// 初始的时候,第一订单先选上,这个时候的最右边界为第一个订单的 second
int cnt = 1, last = q[0].second;
for (int i = 1; i < n; i++) {
// 从第二个订单开始
// 如果当前的 first 已经比最右边界 last 大了
if (q[i].first > last) {
// 可选择的 + 1
cnt++;
// 同时 最右边界 暂时来到 这个的 second
last = q[i].second;
}
// 如果当前的 second 比 last 小,
// 那么就说明 可以把 上一个订单 舍弃,使用更好的 当前订单 (贪心)
// 也就是将 last 变成当前的 second。
if (q[i].second < last)
last = q[i].second;
}
cout << cnt << endl;
return 0;
}