UVa12694 - Meeting Room Arrangement (數論 Math theorm)

題目大意

有一個討論室每天開放 10 小時(0~10)，我們會給你每個會議的開始與結束時間，想請你幫我們在此會議室中塞入多的會議。

題目連結

重點觀念

• 思考到效率提升
• 意識到可以用排序解決

分析

通常比較直覺的寫法是直接對會議的開始與結束時間進行排序，先排序開始在排序結束，從最早的結束時間進行 greedy。

這裡提供一種寫法，我們只需要排序結束時間即可，並且我們用一個變數紀錄討論室最後結束時間(定義 end)。

接下來用 end 去跟每一個會議開始時間做比較，如果會議開始時間比討論室結束時間晚就將答案加一。

原因是由於我們對結束時間排序，因此結束時間越早的則會在越前面，並且我們紀錄了討論室結束時間。如果遇到這種測資也可以避免

• 當前討論室結束時間為 3
• 兩筆資料
  • 2 點開始 4 點結束
  • 3 點開始 4 點結束
• 結論
  我們可以得出討論室結束時間為 3，其中第一筆資料開始時間為 2 點並不符合，而另一筆剛好從 3 點開始因此符合！

參考連結

UVA 12694 by chucs

心得

可惡，我沒辦法在 5 分鐘內寫完RRRR，好難過QQQ。一開始沒有想到這麼好的寫法，而是想到最直接的貪心解，但程式碼確實沒有比 chucs 大大還好看，因此就進行學習與修改。

希望我未來遇到這種問題我都可以寫出漂亮且乾淨的程式碼。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
int n, s, f; //題目資料
vector<pair<int,int>> meet; //輸入題目會議用

int compare(pair<int,int> x, pair<int,int> y){ //從結束時間開始由小到大排序
    return x.second < y.second;
}

int solve(){
    int end = 0, ans = 0; //end 會議開始時間, ans 答案時間
    for(auto it: meet){ //開始 greedy
        if(end <= it.first){ //討論室可以加入此會議
            //cout << it.first << ' ' << it.second << '\n';
            end = it.second; //紀錄討論室結束時間
            ans++; //答案加一
        }
    }
    return ans; //回傳答案
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> n;
    while(n--){ 
        meet.clear(); //需要清除，以免資料被干擾
        while(cin >> s >> f && (s+f!=0)) meet.push_back({s,f}); //不斷讀入資料
        sort(meet.begin(), meet.end(), compare); //排序
        cout << solve() << '\n'; //輸出答案
    }

    return 0;
}