UVA 10020

Đề bài: https://uva.onlinejudge.org/external/100/10020.pdf
Ý tưởng:
Sắp xếp lại các đoạn tăng dần theo tọa độ left và đi xét lần lượt các đoạn theo thứ tự này để chọn ra các đoạn phủ tối thiểu theo quy tắc:

• Đầu tiên, gán giá trị phải nhất hiện tại curr = 0.
• Ở mỗi lần chọn ta sẽ chọn 1 đoạn sao cho đoạn này có tọa độ left nhỏ hơn hoặc bằng giá trị phải nhất hiện tại và tọa độ right là lớn nhất có thể, sau khi chọn đoạn này ta cập nhật lại giá trị curr.

Code:
#include <bits/stdc++.h>
#define oo 1000000007
#define debug(a) cout << #a << ": " << a << endl
#define fto(i, x, y) for (int i = (x); i <= (y); ++i)
#define fdto(i, x, y) for (int i = (x); i >= (y); --i)
#define forit(it, var) for(__typeof(var.begin()) it = var.begin(); it != var.end(); ++it)
#define forrit(rit, var) for(__typeof(var.rbegin()) rit = var.rbegin(); rit != var.rend(); ++rit)
#define FF first
#define SS second
#define ii pair<int, int>
#define vi vector<int>
#define vii vector<ii>
#define ll long long
#define mp make_pair
#define pb push_back
#define maxN 10005
using namespace std;

int main() {
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE
    int nTest;
    scanf("%d", &nTest);
    fto(iTest, 1, nTest) {
        int m, l, r;
        scanf("%d", &m);
        vii a;
        vi ans;
        while (scanf("%d%d", &l, &r) &&(l != 0 || r != 0)) a.pb(mp(l, r));
        sort(a.begin(), a.end());
        int curr = 0, i = 0, cnt = 0;
        while (1) {
            if (i == a.size() || a[i].first > curr) {
                cnt = 0; break;
            }
            int p = i;
            for (; i < a.size(), a[i].first <= curr; ++i) {
                if (a[i].second > a[p].second) p = i;
            }
            curr = a[p].second;
            ++cnt;
            ans.pb(p);
            if (curr >= m) break;
        }
        printf("%d\n", cnt);
        if (cnt > 0) {
            fto(i, 0, (int)ans.size()-1) {
                printf("%d %d\n", a[ans[i]].first, a[ans[i]].second);
            }
        }
        if (iTest < nTest) printf("\n");
    }
    return 0;
}