一、题意

有一个会议室，同一时间只能用来开一次会。
输入若干会议时间区间，输出这个会议室最多能安排多少场会议。

二、解析

经典的区间不相交问题。
由贪心思想：我们希望选出一个区间后，能留下来更长一些的时间长度（这样才有可能选出更多的区间），因此我们按照时间区间的结束点进行从小到大排序，总是先选取最先完成的会议。

三、代码

#include <iostream>
#include <vector>
#include <algorithm>
#define mp make_pair
using namespace std;
int kase;
vector<pair<int, int> > vec;

int main() {
    cin >> kase;
    while(kase --) {
        int x, y;
        vec.clear();
        while(cin >> x >> y && (x || y)) vec.push_back(mp(x, y));
        sort(vec.begin(), vec.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
            return a.second < b.second;
        });
        int ans = 0, cur = 0;
        for(const auto & p : vec) if(p.first >= cur) ans ++, cur = p.second;
        cout << ans << endl;
    }
}

四、归纳

  • 区间问题之区间不相交问题：按右端点排列，然后总是先选取最先完成的时间区间。