题目描述
- 区间分组
给定 N个闭区间 [ai,bi],请你将这些区间分成若干组,使得每组内部的区间两两之间(包括端点)没有交集,并使得组数尽可能小。输出最小组数。
样例
cin>>
3
-1 1
2 4
3 5
cout<<
2
算法1
(贪心) $O(n^2)$
为了输出的是最大值,就要探寻峰值,当要用的时候加一,当不要用的时候就减一。
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int range[N * 2], num = 0, sum = 0, answer = 1, n;
int main(void){
cin >> n;
while(n--){
int left, right;
cin >> left >> right;
range[num++] = left * 2;
range[num++] = right * 2 + 1;
}
sort(range, range + num);
for(int i = 0; i < num; i++){
if(range[i] % 2 == 0) sum++;
else sum--;
answer = max(answer, sum);
}
cout << answer << endl;
return 0;
}