UVA 10020 Minimal coverage

#題目：

給定一個值M，和許多不同的線段

求最少的線段可完整覆蓋0到M

#思路：

從零開始要找第一個線段，該線段的左值必須在零的左邊或等於零

在這個條件下再去尋找擁有最大右值的線段，以此類推

這樣便可確保利用最少的線段填滿0到M

*需考慮無法填滿的兩個情況：

1.尋找線段時，找不到左值符合條件的線段

2.已經用完所有線段後，依然無法填滿(亦即，最大右值的線段的右值小於M)

#include <iostream>
using namespace std;

struct segment{
    int l, r;
};

int main(int argc, const char * argv[]) {
    int cases, M;
    while (cin >> cases) {
        while (cases--) {
            segment seg[100005];
            segment ans[100005];
            cin.get(); //空行
            cin >> M;
            int i = 0;
            while ((cin >> seg[i].l >> seg[i].r)) {
                if (seg[i].l == 0 && seg[i].r == 0) break; //結束
                else if (seg[i].l < 0 && seg[i].r < 0){    //兩端都小於0 不用考慮 直接設為0 0
                    seg[i].l = 0;
                    seg[i].r = 0;
                }
                i++;
            }
            
            int larger_r = 0, mark = 0, count = 0;

            /*用larger_r找有最大r的新片段，mark記錄該片段的index，count計算片段數量*/
            int a = 0; ans[a].l = 0; ans[a].r = 0;//ans紀錄每個片段的值
            
            while (larger_r < M && count < i) {
                for (int j = 0; j < i; j++) {
                    if (seg[j].l <= ans[a].r && seg[j].r > larger_r) {

                        /*新片段的l要小於等於上一個片段的r，再找最大r*/
                        larger_r = seg[j].r;
                        mark = j;
                    }
                }
                if (larger_r == ans[a].r){  //找不到的情況 表示0到Ｍ無法被完整覆蓋
                    count = 0;
                    break;
                }
                else {
                    ans[++a].l = seg[mark].l; ans[a].r = seg[mark].r;
                    count++;
                }
            }
            
            if (larger_r < M || count == 0) cout << '0' << endl;
            else {
                cout << count << endl;
                for (int i = 1; i <= count; i++) {
                    cout << ans[i].l << " " << ans[i].r << endl;
                }
            }
            cout << "\n";
        }
    }
    return 0;
}