本文涉及知识点
贪心 决策包容性
LeetCode757. 设置交集大小至少为2
给你一个二维整数数组 intervals ，其中 intervals[i] = [starti, endi] 表示从 starti 到 endi 的所有整数，包括 starti 和 endi 。
包含集合 是一个名为 nums 的数组，并满足 intervals 中的每个区间都 至少 有 两个 整数在 nums 中。
例如，如果 intervals = [[1,3], [3,7], [8,9]] ，那么 [1,2,4,7,8,9] 和 [2,3,4,8,9] 都符合 包含集合 的定义。返回包含集合可能的最小大小。
示例 1：
输入：intervals = [[1,3],[3,7],[8,9]]
输出：5
解释：nums = [2, 3, 4, 8, 9].
可以证明不存在元素数量为 4 的包含集合。
示例 2：
输入：intervals = [[1,3],[1,4],[2,5],[3,5]]
输出：3
解释：nums = [2, 3, 4].
可以证明不存在元素数量为 2 的包含集合。
示例 3：
输入：intervals = [[1,2],[2,3],[2,4],[4,5]]
输出：5
解释：nums = [1, 2, 3, 4, 5].
可以证明不存在元素数量为 4 的包含集合。
提示：
1 <= intervals.length <= 3000
intervals[i].length == 2
0 <= starti < endi <= 108
决策包容性
令intervals[i1]的end最小。假定其在某个最优解包括的数为x1,x2。我们将x1和x2换成endi1和endi1-1也必定是最优解。
对于 ∀ \forall ∀i 包括x2，那说明begini <= x2 <=endi 。由于 endi1 >=x2 且endi1<=endi。故endi1也包括。
对于 ∀ \forall ∀i 如果包括x1和x2，x1 < x2 <=endi ,故endi1-1 <= endi ,endi1-1 >= x1 。即endi1-1也包括。
故：
setHas 记录已有数字。
按end升序处理，如果setHas包括两个数字，则忽略。
如果包括一个数字，将endi加入。
如果包括0个数字，将endi和endi-1也加入。
cnt=2
如何判断setHas需要多少个数字
it = setHas.lower(begin);
if( it合法&& ⋆ \star ⋆it <= end ){
cnt–;
it++;
如果合法且 ⋆ \star ⋆it <= end ,再–。
时间复杂度：O(nlogn) 二分查找的时间复杂度O(logn)。
错误
{1,3}{3,7}，{5,7}
{5,7}时试图 增加7，但7已经存在。
当end相等的时候begin大的再前面，或end相等时，忽略begin小的。
当setHas有0个数时，自然不包括endi和endi-1。
有一个数时：
如果不存在相等的endi，则setHas一定不包括endi。
如果相等的endi，begini大的在前。 当前一定包括两个数，无需处理。
代码
核心代码
class Solution {
public:int intersectionSizeTwo(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), [&](vector<int>& v1, vector<int>& v2) {return (v1[1] < v2[1])||(( v1[1]== v2[1])&&(v1[0] > v2[0])); });set<int> setHas;for (const auto& v : intervals) {auto it = setHas.lower_bound(v[0]);int cnt = 2;if ((setHas.end() != it) && (*it <= v[1])) {cnt--;it++;if ((setHas.end() != it) && (*it <= v[1])) {cnt--;}}if (cnt >=1 ) {setHas.emplace(v[1]);}if (2 == cnt) {setHas.emplace(v[1]-1);}}return setHas.size();}
};单元测试
template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{Assert::AreEqual(t1, t2);
}
void AssertEx( double t1, double t2)
{auto str = std::to_wstring(t1) + std::wstring(1,32) + std::to_wstring(t2);Assert::IsTrue(abs(t1 - t2) < 1e-5,str.c_str() );
}template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{Assert::AreEqual(v1.size(), v2.size());for (int i = 0; i < v1.size(); i++){Assert::AreEqual(v1[i], v2[i]);}
}template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i = 0; i < vv1.size(); i++){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{vector<vector<int>> intervals;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod00){intervals = { {1,3},{3,7},{8,9} };auto res = Solution().intersectionSizeTwo(intervals);AssertEx(5, res);}TEST_METHOD(TestMethod01){intervals = { {1,3},{1,4},{2,5},{3,5} };auto res = Solution().intersectionSizeTwo(intervals);AssertEx(3, res);}TEST_METHOD(TestMethod02){intervals = { {1,2},{2,3},{2,4},{4,5} };auto res = Solution().intersectionSizeTwo(intervals);AssertEx(5, res);}TEST_METHOD(TestMethod03){intervals = { {1,3},{3,7},{5,7},{7,8} };auto res = Solution().intersectionSizeTwo(intervals);AssertEx(5, res);}};
}
扩展阅读
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关推荐
| 我想对大家说的话 |
|---|
| 《喜缺全书算法册》以原理、正确性证明、总结为主。 |
| 按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
