本文涉及知识点

C++差分数组

LeetCode2406. 将区间分为最少组数

给你一个二维整数数组 intervals ，其中 intervals[i] = [lefti, righti] 表示 闭 区间 [lefti, righti] 。
你需要将 intervals 划分为一个或者多个区间 组 ，每个区间 只 属于一个组，且同一个组中任意两个区间 不相交 。
请你返回 最少 需要划分成多少个组。
如果两个区间覆盖的范围有重叠（即至少有一个公共数字），那么我们称这两个区间是 相交 的。比方说区间 [1, 5] 和 [5, 8] 相交。
示例 1：
输入：intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]]
输出：3
解释：我们可以将区间划分为如下的区间组：

• 第 1 组：[1, 5] ，[6, 8] 。
• 第 2 组：[2, 3] ，[5, 10] 。
• 第 3 组：[1, 10] 。
  可以证明无法将区间划分为少于 3 个组。
  示例 2：
  输入：intervals = [[1,3],[5,6],[8,10],[11,13]]
  输出：1
  解释：所有区间互不相交，所以我们可以把它们全部放在一个组内。
  提示：
  1 <= intervals.length <= 10⁵
  intervals[i].length == 2
  1 <= lefti <= righti <= 10⁶

差分数组

差分数组diff记录各点的区间数，对应的数据数组为a。a[i]的最大值就是结果。下面来证明：
我们a[i]的最大值是x=a[i1]，必须分x个区间组，否则必定有重叠。
令包括i1的所有区间最小的点为x1，包括x1的区间至多x个，故可以放到这x个区域组。
令已经处理的区间中，最小的点为x2，包括x2的全局至多x个，故可以放到这x个区域组。
$⋮$
处理完左边的区间后，类似的方法处理右边的区间。

代码

核心代码

	class Solution {
		public:
			int minGroups(vector<vector<int>>& intervals) {
				const int N = 1'000'000 + 1;
				vector<int> diff(N + 1);
				for (const auto& v : intervals) {
					diff[v[0]]++;
					diff[v[1] + 1]--;
				}
				bool bStart = false;
				int ret = 0;
				int cur = 0;
				for (int i = 0; i <= N; i++) {
					cur += diff[i];
					ret = max(ret, cur);
				}
				return ret;
			}
		};

单元测试

vector<vector<int>> intervals;
		TEST_METHOD(TestMethod11)
		{
			intervals = { {5,10},{6,8},{1,5},{2,3},{1,10} };
			auto res = Solution().minGroups(intervals);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod12)
		{
			intervals = { {1,3},{5,6},{8,10},{11,13} };
			auto res = Solution().minGroups(intervals);
			AssertEx(1, res);
		}