待预约的会议——2023年天大&南开夏令营机试题

#include<bits/stdc++.h>
using namespace std;

int main(){
          
   
    ios::sync_with_stdio(false); cin.tie(nullptr);//加速cin, cout
    int T, n, s, t;
    cin >> T;
    while(T--){
          
   
        cin >> n;
        vector<pair<int, int>> vec;//<time,flag> flag=1开始/-1结束 
        for (int i = 0; i < n; ++i) {
          
   
            cin >> s >> t;
            vec.emplace_back(s, 1);
            vec.emplace_back(t, -1);
        }
        //首先按照时间点从小到大排序，然后按照会议状态的优先级排序（-1 优先于 1），以满足差分的要求。
        sort(vec.begin(), vec.end());
        int ans = 0, sum = 0;
        for (const auto& e : vec) {
          
   
            sum += e.second; //同时进行的会议数量sum,开始+1，结束-1
            ans = max(ans, sum); //维护一个sum的最大值
        }
        cout << ans << endl;
        vec.clear(); // 清空 vector
    }
    return 0;
}

根据输入的会议开始和结束时间，需要确定同时进行的最大会议数量。

使用一个 vector<pair<int, int>> 来存储每个会议的开始和结束时间，其中 pair 中的第二个元素表示会议的状态（1 表示开始，-1 表示结束）。emplace_back(make_pair(s, 1)) 和 emplace_back(s, 1) 都会创建一个新的 pair<int, int> 对象并将其添加到 vector 的末尾。

接下来，代码对 vec 进行排序，首先按照时间点从小到大排序，然后按照会议状态的优先级排序（-1 优先于 1），以满足差分的要求。排序后，会议的开始时间和结束时间按照顺序排列。

vector<pair<int, int>> vec 默认使用默认的 operator< 来进行排序。对于 pair 类型，默认的比较方式是先比较第一个元素，升序排序，如果相等则比较第二个元素，升序排序。因此，在 sort(vec.begin(), vec.end()) 中，会先按照时间点从小到大排序，如果时间点相同，则会按照会议状态的优先级进行排序（-1 优先于 1）。由于这种比较方式已经满足了差分的要求，所以不需要专门重写比较函数。

然后，使用循环遍历 vec，根据会议状态的变化，来计算同时进行的会议数量。通过累加和更新答案 ans，即可得到最大的同时进行的会议数量。(进行模拟：会议室无限多，顺序进行开会操作，计算每一时刻所用的会议室个数sum，维护一个sum的最大值，直至所有会议结束)