(发发同学讲的)首先把所有的区间按照ending从小到大排序,如果ending相同,start靠前的放在前面。貌似pair不是很符合啊。。
所以我们用greater来给pair排序,然后再reserve一下……
然后呢,就是贪婪了,每次都在各个区间的交集那儿取(因为这样可以让取到的元素属于尽可能多的区间),对于两端的区间,如果交集那儿没取够两个,那就随便再取几个(如果还差1个就取1个,如果差两个就取两个)补上。
其实。。看看贪的方法就能看出来。。给vec一个reserve或者不给reserve都是一样的…… 因为中间的那些交集不管是否reserve都是不变的,无非是两边取的时候有点区别。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <memory.h>
using namespace std;
int
main()
{
vector<pair<int, int> > vec;
int nr_intervals;
int seg_begin(0x7FFFFFFF), seg_end(0);
int previous1, previous2;
int nr_elements(0);
//freopen("test.txt", "r", stdin);
ios::sync_with_stdio(false);
cin >> nr_intervals;
for (int i = 0; i != nr_intervals; ++i) {
int t1, t2;
cin >> t1 >> t2;
seg_begin = min(t1, seg_begin);
seg_end = max(t2, seg_end);
vec.push_back(make_pair(t1, t2));
}
sort(vec.begin(), vec.end(), greater<pair<int, int> >());
vec.reserve(vec.size());
previous1 = vec.front().first;
previous2 = vec.front().first + 1;
nr_elements = 2;
for (vector<pair<int, int> >::iterator iter = vec.begin() + 1, iter_end = vec.end(); iter != iter_end; ++iter) {
// Obviously, previous2 > previous1.
if (iter->second < previous1) {
// None in our set is included by range *iter.
nr_elements += 2;
previous1 = iter->first;
previous2 = iter->first + 1;
} else if (iter->second < previous2) {
// It is easy to figure out that iter->second is larger or equal to previous1 if we get here.
nr_elements += 1;
previous2 = previous1;
previous1 = iter->first;
} // Or the entire range specified by *iter is satisfied by our set.
}
cout << nr_elements << endl;
return 0;
}