【区间合并差分栈】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

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