#include #include #include //#define VERBOSE using namespace std; #define MAX_N 150000 int N; class Interval { public: int left, right; Interval(int l = 0, int r = 0) : right(r), left(l) {} }; ostream& operator <<(ostream& os, const Interval& interval) { return os << interval.left << " " << interval.right; } istream& operator >>(istream& is, Interval& interval) { return is >> interval.left >> interval.right; } Interval intervals[MAX_N]; int line[2*MAX_N + 1]; vector dominating_set; int main() { #ifdef EVAL ifstream in("input.txt"); ofstream out("output.txt"); #else istream &in(cin); ostream &out(cout); #endif in >> N; for (int i = 0; i < N; ++i) { in >> intervals[i]; line[intervals[i].left] = -(i+1); line[intervals[i].right] = i+1; } int upto = 0; int cur_right = 0; int cur_left = 0; for (;;) { // cerr << "Coperto fino a " << upto << endl; for ( cur_right = upto; ( cur_right < 2*N + 1 ) && // Cerco l'intervallo che comincia ( ( line[cur_right] <= 0 ) || intervals[line[cur_right]-1].left < upto); ++cur_right ) ; // dopo upto e finisce per primo // cerr << "Estremo destro piu` a sinistra: " << cur_right << endl; if (cur_right == 2*N + 1) break; int rightmost_right = -1; Interval* max_interval; // cerr << "A sinistra parto da " << cur_left << endl; for ( ; ( cur_left <= cur_right ); ++cur_left ) if (line[cur_left] < 0) { // Se qui comincia un intervallo... Interval* iter = &intervals[-line[cur_left] - 1]; if (iter->right > rightmost_right) { // Prendo quello che va piu` a destra rightmost_right = iter->right; max_interval = iter; } } dominating_set.push_back(max_interval); upto = rightmost_right; } out << dominating_set.size() << endl; #ifdef VERBOSE for (vector::iterator iter = dominating_set.begin(); iter != dominating_set.end(); ++iter) out << **iter << endl; #endif }