#include #include #include #include #include #include using namespace std; #define MAX_N 10000 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]; 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]; } int upto = -1; for (;;) { int leftmost_right = INT_MAX; for (Interval* iter = intervals; iter != intervals+N; ++iter) { if ( iter->left > upto ) if (iter->right < leftmost_right) leftmost_right = iter->right; } if (leftmost_right == INT_MAX) break; int rightmost_right = -1; Interval* max_interval; for (Interval* iter = intervals; iter != intervals+N; ++iter) { if ( iter->left > upto && iter->left <= leftmost_right) if ( iter->right > rightmost_right ) { rightmost_right = iter->right; max_interval = iter; } } 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; }