算法可以发掘本质，如：
一，若干师傅和徒弟互有好感，有好感的师徒可以结对学习。师傅和徒弟都只能参加一个对子。如何让对子最多。
二，有无限多1X2和2X1的骨牌，某个棋盘若干格子坏了，如何在没有坏的格子放足够多骨牌。
三，某个单色图，1表示前前景，0表示后景色。每次操作可以将一个1，变成0。如何在最少得操作情况下，使得没有两个1相邻（四连通）。
四，若干路人，有些人是熟人，如何选出最多的人参加实验。为了避免熟人影响实验的效果，参加的人不能是熟人。
一二是二分图的最大匹配，三是二分图的最小点覆盖，四是二分图最大独立集。 而这三者是等效问题。
本文涉及知识点
线段树 有序映射
线段树：就求一乐乎，难写。在超时的边缘。
LeetCode715. Range 模块
Range模块是跟踪数字范围的模块。设计一个数据结构来跟踪表示为 半开区间 的范围并查询它们。
半开区间 [left, right) 表示所有 left <= x < right 的实数 x 。
实现 RangeModule 类:
RangeModule() 初始化数据结构的对象。
void addRange(int left, int right) 添加 半开区间 [left, right)，跟踪该区间中的每个实数。添加与当前跟踪的数字部分重叠的区间时，应当添加在区间 [left, right) 中尚未跟踪的任何数字到该区间中。
boolean queryRange(int left, int right) 只有在当前正在跟踪区间 [left, right) 中的每一个实数时，才返回 true ，否则返回 false 。
void removeRange(int left, int right) 停止跟踪 半开区间 [left, right) 中当前正在跟踪的每个实数。
示例 1：
输入
[“RangeModule”, “addRange”, “removeRange”, “queryRange”, “queryRange”, “queryRange”]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
输出
[null, null, null, true, false, true]
解释
RangeModule rangeModule = new RangeModule();
rangeModule.addRange(10, 20);
rangeModule.removeRange(14, 16);
rangeModule.queryRange(10, 14); 返回 true （区间 [10, 14) 中的每个数都正在被跟踪）
rangeModule.queryRange(13, 15); 返回 false（未跟踪区间 [13, 15) 中像 14, 14.03, 14.17 这样的数字）
rangeModule.queryRange(16, 17); 返回 true （尽管执行了删除操作，区间 [16, 17) 中的数字 16 仍然会被跟踪）
提示：
1 <= left < right <= 109
在单个测试用例中，对 addRange 、 queryRange 和 removeRange 的调用总数不超过 104 次
代码
template<class TSave, class TRecord > class CRangUpdateLineTree { protected: virtual void OnQuery(TSave& save, int iSaveLeft, int iSaveRight) = 0; virtual void OnUpdate(TSave& save, int iSaveLeft,int iSaveRight, const TRecord& update) = 0; virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) = 0; virtual void OnUpdateRecord(TRecord& old, const TRecord& newRecord) = 0; }; template<class TSave, class TRecord > class CTreeRangeLineTree : public CRangUpdateLineTree<TSave, TRecord> { protected: struct CTreeNode { int Cnt()const { return m_iMaxIndex - m_iMinIndex + 1; } int m_iMinIndex; int m_iMaxIndex; TRecord record; TSave data; CTreeNode* m_lChild = nullptr, * m_rChild = nullptr; }; CTreeNode* m_root; TSave m_tDefault; TRecord m_tRecordDef; public: CTreeRangeLineTree(int iMinIndex, int iMaxIndex, TSave tDefault,TRecord tRecordDef) { m_tDefault = tDefault; m_tRecordDef = tRecordDef; m_root = CreateNode(iMinIndex, iMaxIndex); } void Update(int iLeftIndex, int iRightIndex, TRecord value) { Update(m_root, iLeftIndex, iRightIndex, value); } TSave QueryAll() { return m_root->data; } void Query(int leftIndex, int leftRight) { Query(m_root, leftIndex, leftRight); } protected: void Query(CTreeNode* node, int iQueryLeft, int iQueryRight) { if ((node->m_iMinIndex >= iQueryLeft) && (node->m_iMaxIndex <= iQueryRight)) { this->OnQuery(node->data,node->m_iMinIndex,node->m_iMaxIndex); return; } if (1 == node->Cnt()) {//没有子节点 return; } CreateChilds(node); Fresh(node); const int mid = node->m_iMinIndex + (node->m_iMaxIndex - node->m_iMinIndex) / 2; if (mid >= iQueryLeft) { Query(node->m_lChild, iQueryLeft, iQueryRight); } if (mid + 1 <= iQueryRight) { Query(node->m_rChild, iQueryLeft, iQueryRight); } } void Update(CTreeNode* node, int iOpeLeft, int iOpeRight, TRecord value) { const int& iSaveLeft = node->m_iMinIndex; const int& iSaveRight = node->m_iMaxIndex; if ((iOpeLeft <= iSaveLeft) && (iOpeRight >= iSaveRight)) { this->OnUpdate(node->data, iSaveLeft, iSaveRight, value); this->OnUpdateRecord(node->record, value); return; } if (1 == node->Cnt()) {//没有子节点 return; } CreateChilds(node); Fresh(node); const int mid = node->m_iMinIndex + (node->m_iMaxIndex - node->m_iMinIndex) / 2; if (mid >= iOpeLeft) { this->Update(node->m_lChild, iOpeLeft, iOpeRight, value); } if (mid + 1 <= iOpeRight) { this->Update(node->m_rChild, iOpeLeft, iOpeRight, value); } // 如果有后代，至少两个后代 this->OnUpdateParent(node->data, node->m_lChild->data, node->m_rChild->data,node->m_iMinIndex,node->m_iMaxIndex); } void CreateChilds(CTreeNode* node) { if (nullptr != node->m_lChild) { return; } const int iSaveLeft = node->m_iMinIndex; const int iSaveRight = node->m_iMaxIndex; const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2; node->m_lChild = CreateNode(iSaveLeft, mid); node->m_rChild = CreateNode(mid + 1, iSaveRight); } CTreeNode* CreateNode(int iMinIndex, int iMaxIndex) { CTreeNode* node = new CTreeNode; node->m_iMinIndex = iMinIndex; node->m_iMaxIndex = iMaxIndex; node->data = m_tDefault; node->record = m_tRecordDef; return node; } void Fresh(CTreeNode* node) { if (m_tRecordDef == node->record) { return; } CreateChilds(node); Update(node->m_lChild, node->m_lChild->m_iMinIndex, node->m_lChild->m_iMaxIndex, node->record); Update(node->m_rChild, node->m_rChild->m_iMinIndex, node->m_rChild->m_iMaxIndex, node->record); node->record = m_tRecordDef; } }; template<class TSave=int, class TRecord =int > class CMyTreeRangeLineTree : public CTreeRangeLineTree<TSave, TRecord> { public: using CTreeRangeLineTree<TSave, TRecord>::CTreeRangeLineTree; bool queryRange(int left, int right) { m_bHas = true; CTreeRangeLineTree<TSave, TRecord>::Query(left, right); return m_bHas; } protected: bool m_bHas = true; virtual void OnQuery(TSave& save, int iSaveLeft, int iSaveRight) override { m_bHas &= (save == (iSaveRight - iSaveLeft + 1)); } virtual void OnUpdate(TSave& save, int iSaveLeft, int iSaveRight, const TRecord& update) override { save = update*(iSaveRight-iSaveLeft+1); } virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) override { par = left + r; } virtual void OnUpdateRecord(TRecord& old, const TRecord& newRecord) override { old = newRecord; } }; class RangeModule { public: RangeModule() :m_treeLine(1, 1'000'000'000, 0, -1) { } void addRange(int left, int right) { m_treeLine.Update(left, right-1, 1); } bool queryRange(int left, int right) { return m_treeLine.queryRange(left, right - 1); } void removeRange(int left, int right) { m_treeLine.Update(left, right-1, 0); } CMyTreeRangeLineTree<> m_treeLine; };
有序映射
class RangeModule { public: RangeModule() { } void addRange(int left, int right) { auto it1 = m_mLeftRight.lower_bound(left); auto it2 = m_mLeftRight.upper_bound(right); if (it1 != m_mLeftRight.begin()) { auto tmp = it1; --tmp; if (tmp->second >= left) { left = tmp->first; --it1; } } if (it2 != m_mLeftRight.begin()) { auto tmp = it2; --tmp; if (tmp->second > right) { right = tmp->second; } } m_mLeftRight.erase(it1, it2); m_mLeftRight[left] = right; } bool queryRange(int left, int right) { auto it1 = m_mLeftRight.upper_bound(left); if (it1 != m_mLeftRight.begin()) { auto tmp = it1; tmp--; return tmp->second >= right; } return false; } void removeRange(int left, int right) { auto it1 = m_mLeftRight.lower_bound(left); auto it2 = m_mLeftRight.upper_bound(right); int iNewLeft = -1; if (it1 != m_mLeftRight.begin()) { auto tmp = it1; --tmp; if (tmp->second >= left) { iNewLeft = tmp->first; } } int iNewRight = -1; if (it2 != m_mLeftRight.begin()) { auto tmp = it2; --tmp; if (tmp->second > right) { iNewRight = tmp->second; } } m_mLeftRight.erase(it1, it2); if (-1 != iNewLeft) { m_mLeftRight[iNewLeft] = left; } if (-1 != iNewRight) { m_mLeftRight[right] = iNewRight; } } std::map<int, int> m_mLeftRight; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业 |
。也就是我们常说的专业的人做专业的事。 |
|如果程序是一条龙，那算法就是他的是睛|
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
