AcWing 3818. 餐厅(vector)
原题链接
简单
作者:
自由基
,
2021-08-27 22:33:32
,
所有人可见
,
阅读 327
贪心
$O(n)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
const int N = 10010;
int n;
vector<PII> segs;
int main( ) {
cin >> n;
while( n -- )
{
int l, r;
scanf("%d%d", &l, &r);
segs.push_back({l,r});
}
sort(segs.begin(), segs.end());
int res = 0;
int st = -2e9, ed = -2e9;
for( auto seg : segs )
{
// 当前区间右端点小于下一个区间的左端点,更新
if( ed < seg.first )
{
res++;
st = seg.first, ed = seg.second;
}
else
{ // 当前区右左端点小于下个区间的右端点,直接选用当前区间(贪心)
if( ed < seg.second ) continue;
// seg.second - seg.first <= ed - st 其实也可省略
else if( ed >= seg.second && seg.second - seg.first <= ed - st )
{
st = seg.first, ed = seg.second;
}
}
}
cout << res << endl;
return 0;
}