本文涉及的基础知识点

二分查找算法合集
离线查询

LeetCode1851包含每个查询的最小区间

给你一个二维整数数组 intervals ，其中 intervals[i] = [lefti, righti] 表示第 i 个区间开始于 lefti 、结束于 righti（包含两侧取值，闭区间）。区间的 长度 定义为区间中包含的整数数目，更正式地表达是 righti - lefti + 1 。
再给你一个整数数组 queries 。第 j 个查询的答案是满足 lefti <= queries[j] <= righti 的 长度最小区间 i 的长度 。如果不存在这样的区间，那么答案是 -1 。
以数组形式返回对应查询的所有答案。
示例 1：
输入：intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
输出：[3,3,1,4]
解释：查询处理如下：

• Query = 2 ：区间 [2,4] 是包含 2 的最小区间，答案为 4 - 2 + 1 = 3 。
• Query = 3 ：区间 [2,4] 是包含 3 的最小区间，答案为 4 - 2 + 1 = 3 。
• Query = 4 ：区间 [4,4] 是包含 4 的最小区间，答案为 4 - 4 + 1 = 1 。
• Query = 5 ：区间 [3,6] 是包含 5 的最小区间，答案为 6 - 3 + 1 = 4 。
  示例 2：

输入：intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
输出：[2,-1,4,6]
解释：查询处理如下：

• Query = 2 ：区间 [2,3] 是包含 2 的最小区间，答案为 3 - 2 + 1 = 2 。
• Query = 19：不存在包含 19 的区间，答案为 -1 。
• Query = 5 ：区间 [2,5] 是包含 5 的最小区间，答案为 5 - 2 + 1 = 4 。
• Query = 22：区间 [20,25] 是包含 22 的最小区间，答案为 25 - 20 + 1 = 6 。
  参数范围：
  1 <= intervals.length <= 105
  1 <= queries.length <= 105
  intervals[i].length == 2
  1 <= lefti <= righti <= 107
  1 <= queries[j] <= 107

代码

核心代码

class Solution {
public:
vector minInterval(vector<vector>& intervals, vector& queries) {
m_c = queries.size();
std::multimap <int, int> mBeginLen, mEndLen;
for (const auto& v : intervals)
{
const int len = v[1] - v[0] + 1;
mBeginLen.emplace(v[0], len);
}
vector indexs(m_c);
iota(indexs.begin(), indexs.end(), 0);
sort(indexs.begin(), indexs.end(), [&](const int& i1, const int& i2) {return queries[i1] < queries[i2]; });
auto it1 = mBeginLen.begin();
std::multiset setLen;
vector vRet(m_c);
for (const auto& i : indexs)
{
while ((it1 != mBeginLen.end()) && (it1->first <= queries[i]))
{
setLen.emplace(it1->second);
mEndLen.emplace(it1->first + it1->second - 1, it1->second);
it1++;
}
while (mEndLen.size() && (mEndLen.begin()->first < queries[i]))
{
setLen.erase(setLen.find(mEndLen.begin()->second));
mEndLen.erase(mEndLen.begin());
}
vRet[i] = setLen.size() ? *setLen.begin() : -1;
}
return vRet;
}
int m_c;
};

测试用例

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
assert(v1[i] == v2[i]);
}
}

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

int main()
{
vector<vector> intervals;
vector queries, res;
{
intervals = { {1,4},{2,4},{3,6},{4,4} };
queries = { 2,3,4,5 };
Solution slu;
auto res = slu.minInterval(intervals, queries);
Assert(vector{ 3,3,1,4 }, res);
}
{
intervals = { {2,3},{2,5},{1,8},{20,25} };
queries = { 2,19,5,22 };
Solution slu;
auto res = slu.minInterval(intervals, queries);
Assert(vector{2, -1, 4, 6}, res);
}
//CConsole::Out(res);
}

二分查找

class Solution {
public:
	vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
		std::map<int,vector<int>> mBeginEndToLen;
		m_c = queries.size();		
		for (const auto& v : intervals)
		{
			const int len = v[1] - v[0] + 1;
			mBeginEndToLen[v[0]].emplace_back(len);
			mBeginEndToLen[v[1] + 1].emplace_back(-len);
		}
		std::multiset<int> setLen;
		std::map<int, int> mPosLen;
		mPosLen[-1] = -1;
		for (const auto& [pos, v] : mBeginEndToLen)
		{
			for (const auto& n : v)
			{
				if (n > 0)
				{
					setLen.emplace(n);
				}
				else
				{
					setLen.erase(setLen.find(-n));
				}
			}
			mPosLen[pos] = setLen.size() ? *setLen.begin() : -1;
		}

		vector<int> vRet;
		for (const auto& i : queries)
		{
			auto it = mPosLen.upper_bound(i);
			vRet.emplace_back(std::prev(it)->second);
		}
		return vRet;
	}
	int m_c;
};

2023年3月代码

template
bool SortVecVec(const vector& v1, const vector& v2)
{
return v1[ArrIndex] < v2[ArrIndex];
};
class Solution {
public:
vector minInterval(vector<vector>& intervals, vector& queries) {
vector indexs;
for (int i = 0; i < queries.size(); i++)
{
indexs.emplace_back(i);
}
std::sort(indexs.begin(), indexs.end(), [&queries](const int& i1, const int& i2)
{
return queries[i1] < queries[i2];
});
std::sort(intervals.begin(), intervals.end(), SortVecVec<0>);
std::map<int, std::unordered_set> mLenEnd, mEndLen;
int j = 0;
vector vRet(indexs.size());
for (int i1 = 0; i1 < indexs.size(); i1++)
{
const int i = indexs[i1];
const int& q = queries[i];
//删除末端小于当前查询的区间
while (mEndLen.size() && (mEndLen.begin()->first < q))
{
const int iEnd = mEndLen.begin()->first;
for (const auto& len : mEndLen.begin()->second)
{
mLenEnd[len].erase(iEnd);
if (0 == mLenEnd[len].size())
{
mLenEnd.erase(len);
}
}
mEndLen.erase(iEnd);
}
//增加首端小于等于q，末端大于等于q
while ((j < intervals.size()) && (intervals[j][0] <= q))
{
if (intervals[j][1] >= q)
{
const int end = intervals[j][1];
const int len = end - intervals[j][0] + 1;
mLenEnd[len].insert(end);
mEndLen[end].insert(len);
}
j++;
}
vRet[i] = (mLenEnd.size() ? mLenEnd.begin()->first : -1);
}
return vRet;
}
};

优化第一版

将intervals排序后，可以省略mBeginLen。mEndLen和setLen可以合并成mLenEnd。当end小于当前查询值时，不必马上从mLenEnd删除，获取最小长度的时候，再删除。术语叫：延迟删除，如果用优先队列则必须用此技巧。

class Solution {
public:
	vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
		m_c = queries.size();
		vector<int> indexs(m_c);
		iota(indexs.begin(), indexs.end(), 0);
		sort(indexs.begin(), indexs.end(), [&](const int& i1, const int& i2) {return queries[i1] < queries[i2]; });
		sort(intervals.begin(), intervals.end(), [&](const auto& v1, const auto& v2) {return v1[0] < v2[0]; });
		std::multimap<int, int> mLenEnd;
		vector<int> vRet(m_c);
		int left = 0;
		for (const auto& i : indexs)
		{
			while ((left < intervals.size()) && (intervals[left][0] <= queries[i]))
			{
				mLenEnd.emplace(intervals[left][1]- intervals[left][0]+1, intervals[left][1]);
				left++;
			}
			while (mLenEnd.size() && (mLenEnd.begin()->second < queries[i]))
			{
				mLenEnd.erase(mLenEnd.begin());
			}
			vRet[i] = mLenEnd.size() ? mLenEnd.begin()->first : -1;
		}
		return vRet;
	}
	int m_c;
};