ime Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 14048 | Accepted: 5963 |
Description
An integer interval [a,b], a < b, is a set of all consecutive integers beginning with a and ending with b.
Write a program that: finds the minimal number of elements in a set containing at least two different integers from each interval.
Write a program that: finds the minimal number of elements in a set containing at least two different integers from each interval.
Input
The first line of the input contains the number of intervals n, 1 <= n <= 10000. Each of the following n lines contains two integers a, b separated by a single space, 0 <= a < b <= 10000. They are the beginning and the end of an interval.
Output
Output the minimal number of elements in a set containing at least two different integers from each interval.
Sample Input
4 3 6 2 4 0 2 4 7
Sample Output
4
先把区间按最后一个数从小到大排列,然后取出第i个区间最后两位数left,right;
若第i+1个区间包含了这两个元素,则跳到下一个区间所取的元素个数+0
若第i+1个区间只包含了这两个元素中的一个(由于有序,所以必定是包含right),则取第i个区间的最后一个元素,所取的元素个数+1。为了方便下一区间的比较,更新left,right的值,使他们为当前V集合中最后的两个元素。
若第i+1个区间没有包含这两个元素,则第i+1个区间的最后两个元素,所取的元素个数+2。为了方便下一区间的比较,更新left,right的值,使他们为当前V集合中最后的两个元素。
left初始化为第一个区间的最后倒数第2个元素
right初始化为第一个区间的最后的元素
所取的元素个数初始化为2 (就是left,right)
#include<iostream> #include<algorithm> #include<stdlib.h> using namespace std; struct node { int f,r; }h[10005]; int cmp(node a,node b) { if(a.r==b.r) return a.f<b.f; else return a.r<b.r; } int main() { int n; while(cin>>n) { for(int i=0;i<n;i++) { cin>>h[i].f>>h[i].r; } sort(h,h+n,cmp); int left,right; left=h[0].r-1;right=h[0].r; int cnt=2;//初始化为2,就是最初的left,right; for(int i=1;i<n;i++) { if((h[i].f<=left)&&(left<=h[i].r)&&(h[i].f<=right)&&(right<=h[i].r))//两个数都包含的情况 continue; else if((h[i].f<=right)&&(right<=h[i].r))//包含一个数 { left=right;right=h[i].r;cnt++;//更新left,right; } else { left=h[i].r-1;right=h[i].r;cnt+=2; } } cout<<cnt<<endl; } return 0; }