[UVA] 10020 - Minimal Coverage

題目鏈結

題意：

給一個數字m表示給你一個區間0到m

接著給你一堆線段，
輸入 0 0表示線段輸入結束，

1    (區間0到1)
-1 0 (線段1)
-5 -3 (線段2)
2 5 (線段3)
0 0 (線段輸入結束)

若給的線段不能覆蓋該區間則輸出0，
若可以覆蓋的話，輸出最少需要多少線段，以及需要用到那些線段。
測資間要有空行！最後一筆後面不用空行！

我的作法：

貪婪
先將所有線段依左端點 x 座標做排序，
start從0開始，
遍歷全部的 x < start 線段，找到一右端點 x 座標最大的線段，
接著更新start 為 其右端點，
直到覆蓋整個區間，
如果找不到x < start的線段，表示無法覆蓋，直接輸出0。

--------------------------------------------------
/* 20151102
 * hanting
 * UVa 10020 - Minimal Coverage
 * C++
 */
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Line
{
    int first, second;
    bool operator < (const Line &B)const
    {
        return second > B.second or (second == B.second and first < B.first);
    }
};
vector<Line> ans;
bool cover(vector<Line> &line, int M)
{
    sort(line.begin(), line.end());
    int Start = 0, End = M;
    while(Start < End)
    {
        for(int i = 0; i < line.size(); i++)
        {
            if(line[i].first <= Start and line[i].second >= Start)
            {
                ans.push_back(line[i]);
                Start = line[i].second;
                line.erase(line.begin()+i);
                break;
            }
            else if(i == line.size()-1) return false;
        }
    }
    return true;
}
int main()
{
    int testCase = 0;
    cin >> testCase;
    while(testCase--)
    {
        ans.clear();
        int M;
        cin >> M;
        int left, right;
        vector<Line> line;
        while(cin >> left >> right and left+right)
        {
            line.push_back(Line{left, right});
        }
        if(cover(line, M))
        {
            cout << ans.size() << endl;
            for(int i = 0; i < ans.size(); i++)
            {
                cout << ans[i].first << " " << ans[i].second << endl;
            }
        }
        else
        {
            cout << 0 << endl;
        }
        if(testCase) cout << endl;
    }
    return 0;
}