题目
给你一个二维整数数组 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& intervals, vector& queries) { m_c = queries.size(); std::multimap 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 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& 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::mapunordered_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; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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
