区间分组

题目连接：https://www.acwing.com/problem/content/908/

题目描述

给定 N 个闭区间 [ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。
输出最小组数。

输入描述

第一行包含整数 N，表示区间数。
接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。

输出描述

输出一个整数，表示最小组数。
1≤N≤105
−109≤ai≤bi≤109

示例

输入

3
-1 1
2 4
3 5

输出

2

分析

算法过程

本题算法过程如下：

1. 将每个区间按照左端点从小到大进行排序。
2. 从前往后枚举区间，将该区间的左端点与各组右界的最小值作比较，大于等于则加入该组并更新该组右界，小于则新开一组。

各组右界的最小值是通过维护一个小根堆实现的，详见代码。

证明

记最优解的组数为ans，该算法的解的组数为cnt。

显然，该算法得到的方案是合法的，因此有ans<=cnt。

cnt的实际意义是有cnt个区间有重合部分，即这cnt个区间必在不同的组，因此有ans>=cnt。

综上，ans==cnt，证毕。

AC代码

---

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <functional>
using namespace std;

typedef pair<int, int> P;
const int N = 1e5 + 10;
int n;
P a[N];

int main()
{
	cin >> n;
	for (int i = 0; i < N; i++)
	{
		int l, r;
		cin >> l >> r;
		a[i].first = l;
		a[i].second = r;
	}
	sort(a, a + n);
	priority_queue<int, vector<int>, greater<int>> heap;
	for (int i = 0; i < n; i++)
	{
		if (heap.empty() || heap.top() >= a[i].first)
			heap.push(a[i].second);
		else
		{
			heap.pop();
			heap.push(a[i].second);
		}
	}
	cout << heap.size() << endl;
	return 0;
}