#include #include #include #include #include #include using namespace std; #define MAX_N 100000 int N; class Interval { public: int left, right; Interval(int l = 0, int r = 0) : right(r), left(l) {} struct less_left : public binary_function { bool operator() (const Interval* i1, const Interval* i2) { return i1->left < i2->left; } }; struct less_right : public binary_function { bool operator() (const Interval* i1, const Interval* i2) { return i1->right < i2->right; } }; }; 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]; Interval* intervals_lo[MAX_N]; // Intervalli ordinati per estremo sinistro vector dominating_set; int main() { #ifdef EVAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif cin >> N; for (int i = 0; i < N; ++i) { cin >> intervals[i]; intervals_lo[i] = &intervals[i]; } sort(intervals_lo, intervals_lo+N, Interval::less_left()); int upto = -1; int leftmost_int_in_lo = 0; for (;;) { // cerr << "Coperto fino a " << upto << endl; int leftmost_right = INT_MAX; // cout << "Parto da: " << intervals_lo[leftmost_int_in_lo]->left << endl; for (int i = leftmost_int_in_lo; i < N; ++i) { Interval* iter = intervals_lo[i]; if (iter->left > upto) if (iter->right < leftmost_right) leftmost_right = iter->right; } // cerr << "Estremo destro piu` a sinistra: " << leftmost_right << endl; if (leftmost_right == INT_MAX) break; int rightmost_right = -1; Interval* max_interval; int next_leftmost, i; for (i = leftmost_int_in_lo; i < N; ++i) { Interval* iter = intervals_lo[i]; //if (iter->left > upto) // E qui casca l'asino if ( iter->left <= leftmost_right) { if ( iter->right > rightmost_right ) { rightmost_right = iter->right; max_interval = iter; } } else break; } leftmost_int_in_lo = i; // Dopo ripartiamo da dove ora ci siamo fermati (Ottimizzazione non necessaria per l'ottimalita`) dominating_set.push_back(max_interval); upto = rightmost_right; } cout << dominating_set.size() << endl; for (vector::iterator iter = dominating_set.begin(); iter != dominating_set.end(); ++iter) cout << (*iter)->left << " " << (*iter)->right << endl; }