题目

思路

• 依然可以联想气球射箭问题，现在等于在问，一根箭可以最多可以同时射中多少气球。
• 这个观点可以这么理解，可以想象成教室，一个区间的左端点代表活动开始，右端点表示活动结束，如果同时有两个活动，那么必须要用到两个教室。教室在活动开始的时候开一个下来，活动结束的时候关掉一个，那么，同时在运行的最大数量的教室，就是需要求的最小的分组。（在同一个教室里进行的活动可以视为一组，那么一组的教室必然是时间上不重合的）
• 所以说，这个问题就是在问，一根箭可以最多射中多少气球。
• 具体到代码落实，可以无视左右端点开始排序，排序出来的点记住是左端点还是右端点即可，然后按排序后的顺序遍历，遇到左端点就加一个房间，遇到右端点就关闭一个房间。

  代码

  ```cpp

  include

  include

using namespace std;

const int N = 2e5 + 5;

bool cmp (pair a, pair b) { if (a.first < b.first) { return true; } else if (a.first == b.first) { // 如果两个数字相同，那么先就进行开的操作，因为不允许端点重合。 return a.second == false; } return false; }

int main() { int n = 0; cin >> n; pair nums[N]; for (int i = 0; i < 2 * n; ) { int l = 0, r = 0; cin >> l >> r; nums[i++] = {l, false}; nums[i++] = {r, true}; }

sort(nums, nums + 2 * n, cmp);
// 想象成活动安排教室内的问题
// 活动开始就安排一个，结束就关闭一个，同时在线的最多教室数量就是分组数量
// 可以保证一个教室里面的所有活动都是不重合的，也就是区间不重合。
int rooms = 0, max_rooms = -1;
for (int i = 0; i < 2 * n; i++) {
    if (nums[i].second == false) {
        rooms++;
        max_rooms = max(max_rooms, rooms);
    } else {
        rooms--;
    }
}
cout << max_rooms << endl; 
return 0;

}

```