【区间合并差分栈】3169. 无需开会的工作日

本文主要是介绍【区间合并差分栈】3169. 无需开会的工作日，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本文涉及知识点

区间合并
差分数组（大约2024年7月1号发)

LeetCode3169. 无需开会的工作日

给你一个正整数 days，表示员工可工作的总天数（从第 1 天开始）。另给你一个二维数组 meetings，长度为 n，其中 meetings[i] = [start_i, end_i] 表示第 i 次会议的开始和结束天数（包含首尾）。
返回员工可工作且没有安排会议的天数。
注意：会议时间可能会有重叠。

示例 1：
输入：days = 10, meetings = [[5,7],[1,3],[9,10]]
输出：2
解释：
第 4 天和第 8 天没有安排会议。
示例 2：
输入：days = 5, meetings = [[2,4],[1,3]]
输出：1
解释：
第 5 天没有安排会议。
示例 3：
输入：days = 6, meetings = [[1,6]]
输出：0
解释：
所有工作日都安排了会议。
提示：
1 <= days <= 10⁹
1 <= meetings.length <= 10⁵
meetings[i].length == 2
1 <= meetings[i][0] <= meetings[i][1] <= days

差分

days最大10⁹，所以不能有差分数组，只能用差分map，求和的需要有序。
统计开会的时间，比不开会的时间简单。
mDiff[si]++ mDiff[ei+1]-- 表示[si,ei] 一场会议。
$\forall$ mDiff的键 key,其下一个键为nkey。
则 $\forall$ k $\in$ [key,nkey) mDiff[k]都为0，省略。
即：
$\sum_{i:0}^{key}mDiff[i] \quad = \sum_{i:0}^{k}mDiff[i]$
如果x不为0，则[key,nkey)全部要开会。

核心代码

class Solution {
public:int countDays(int days, vector<vector<int>>& meetings) {map<int, int> mDiff;for (const auto& v : meetings) {mDiff[v[0]]++;mDiff[v[1] + 1]--;}int iRet = 0;int sum = 0;for (auto it = mDiff.begin(); std::next(it) != mDiff.end(); ++it) {auto itNext = std::next(it);sum += it->second;if (sum > 0) {iRet += itNext->first - it->first;}}return  days - iRet;}
};

单元测试

template<class T1,class T2>
void AssertEx(const T1& t1, const T2& t2)
{Assert::AreEqual(t1 , t2);
}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
{int days;vector<vector<int>> meetings;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod1){days = 5, meetings = { {2,4},{1,3} };auto res = Solution().countDays(days, meetings);AssertEx(1, res);}};
}

封装类

template<class KEY=int,class VALUE=int>
class CMapDiff
{
public:void Set(KEY left, KEY rExclue, VALUE value) {m_mDiff[left]+= value;m_mDiff[rExclue]-= value;}vector<pair<KEY, VALUE>> Ans()const {vector<pair<KEY, VALUE>> res;VALUE sum = 0;for (const auto& [key,value]: m_mDiff) {			sum += value;res.emplace_back(make_pair(key, sum));}return res;}
protected:map<KEY, VALUE> m_mDiff;
};
class Solution {
public:int countDays(int days, vector<vector<int>>& meetings) {CMapDiff mDiff;for (const auto& v : meetings) {mDiff.Set(v[0], v[1] + 1,1);}auto v = mDiff.Ans();int iRet = 0;for (int i = 0; i + 1 < v.size(); i++) {if( v[i].second > 0 ){ iRet += v[i + 1].first - v[i].first; }			}return  days - iRet;}
};

差分（旧版）

值相同的区间进行了合并，没多大意义。

class Solution {
public:int countDays(int days, vector<vector<int>>& meetings) {map<int, int> mDiff;for (const auto& v : meetings) {mDiff[v[0]]++;mDiff[v[1]+1]--;}vector<pair<int, int>> v;if (1 != mDiff.begin()->first) {v.emplace_back(make_pair(1, 0));}int sum = 0;for (const auto& [day, cnt] : mDiff) {sum += cnt;v.emplace_back(day, (sum>0));}		vector<pair<int, int>> v1;v1.emplace_back(v[0]);for (int i = 1; i < v.size(); i++) {if (v[i].second != v1.back().second) {v1.emplace_back(v[i]);}}if (v1.back().first <= days) {v1.emplace_back(make_pair(days + 1, 0));}int ret = 0;for (int i = 0; i + 1 < v1.size(); i++) {if (0 == v1[i].second) {ret += v1[i + 1].first - v1[i].first;}}return ret;}
};

区间合并

先按开始时间的升序排序。依次入栈，如果当前元素和栈顶元素能合并则合并：开始时间不变，终止时间取两者最大值；否则，直接入栈。

template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{*seft = max(*seft, other);
}class Solution {
public:int countDays(int days, vector<vector<int>>& meetings) {sort(meetings.begin(), meetings.end(), [&](const auto& v1, const auto& v2) {return v1[0] < v2[0]; });stack<pair<int, int>> sta;for (const auto& v : meetings) {if (sta.empty() || (sta.top().second < v[0])) {sta.emplace(make_pair(v[0], v[1] + 1));}else {MaxSelf(&sta.top().second, v[1] + 1);}}int iRet = 0;while (sta.size()) {iRet += sta.top().second - sta.top().first;sta.pop();}return  days - iRet;}
};

封装后

class CIntervalMerging
{
public:CIntervalMerging( vector<vector<int>> vInterval,bool bIncludeEnd) {sort(vInterval.begin(), vInterval.end(), [&](const auto& v1, const auto& v2) {return v1[0] < v2[0]; });for (const auto& v : vInterval) {if (V.empty() || (V.back().second < v[0])) {V.emplace_back(make_pair(v[0], v[1] + bIncludeEnd));}else {V.back().second = max(V.back().second, v[1] + bIncludeEnd);}}}vector<pair<int, int>> V;
};
class Solution {
public:int countDays(int days, vector<vector<int>>& meetings) {	CIntervalMerging im(meetings, true);int iRet = std::accumulate(im.V.begin(), im.V.end(), 0, [](auto val, auto pr) {return val + pr.second - pr.first; });return  days - iRet;}
};

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛