挑选代表
挑选代表
http://www.nowcoder.com/questionTerminal/c563cc42459d49d5923b3460ba142cf8
题目难度：三星
考察点：贪心
方法：贪心
1.分析：
这个题我们再来明确一下题意，有n个闭区间[a,b]，现在需要在每个闭区间中选择两个数，要求的是选出来的数的个数最少，拿样例来说：
4 4 7 2 4 0 2 3 6
可以从第一个区间中选择：4,5,6,7
可以从第二个区间中选择：2,3,4
可以从第三个区间中选择：0,1,2
可以从第四个区间中选择：3,4,5,6
那么显然我们可以选出四个数字1,2,4,5，这样能够保证每个区间能够选择两个数且选择出来的个数是最少的是4个。即:
第一个区间选择的是4和5
第二个区间选择的是2和4
第三个区间选择的是1和2
第四个区间选择的是4和5
我们可以选择贪心的做法，首先按照右端点进行排序，若右端点相同，则按照左端点从小到大排序。这样就可以保证，如果给出的n个区间存在包含关系，那么被包含的区间一定出现在包含区间之上。接下来，如果条件是至少选择一个数的话，就只要选择区间的右端点即可。那么现在是至少选择两个数，那么我们可以进行一些判断，首先用l,r表示上一个处理的区间坐标，如果当前区间与上一个区间即[l,r]存在交叉关系，那么如果满足r-a[i].x < 1，即它们正好只交叉了一个点，此时ans就要+1，且更新r= a[i].y。如果两个区间不存在交叉关系，即是相互隔离的，那么就更新ans+=2，且更新l = a[i].x; r = a[i].y，直到遍历完整个区间，然后输出ans即可。 算法实现：
(1). 输入n个区间的起始坐标。 (2). 将这n个区间按照右端点进行从小到大排序。
(3). 按照上述的贪心做法进行处理，得到ans。
(4). 输出结果ans。
2.复杂度分析：
时间复杂度：O(n*log(n))空间复杂度：O(n)
3.代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4+5;
struct Node {
int x, y;
}a[MAXN];
bool cmp(Node A, Node B) {
if(A.y == B.y) return A.x < B.x;
return A.y < B.y;
}
int main(){
int n; cin>>n;
for(int i=0; i<n; i++) cin>>a[i].x>>a[i].y;
sort(a, a+n, cmp);
int ans = 2, l = a[0].x, r = a[0].y;
for(int i=1; i<n; i++) {
if(r >= a[i].x) {
if(r-a[i].x < 1) {
ans++;
r = a[i].y;
}
}
else {
ans += 2;
l = a[i].x;
r = a[i].y;
}
}
cout<<ans<<endl;
return 0;
}
