436. Find Right Interval
Find right interval
2023-09-11 14:22:45 时间
Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the "right" of i.
For any interval i, you need to store the minimum interval j's index, which means that the interval j has the minimum start point to build the "right" relationship for interval i. If the interval j doesn't exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.
Note:
- You may assume the interval's end point is always bigger than its start point.
- You may assume none of these intervals have the same start point.
Example 1:
Input: [ [1,2] ] Output: [-1] Explanation: There is only one interval in the collection, so it outputs -1.
Example 2:
Input: [ [3,4], [2,3], [1,2] ] Output: [-1, 0, 1] Explanation: There is no satisfied "right" interval for [3,4]. For [2,3], the interval [3,4] has minimum-"right" start point; For [1,2], the interval [2,3] has minimum-"right" start point.
Example 3:
Input: [ [1,4], [2,3], [3,4] ] Output: [-1, 2, -1] Explanation: There is no satisfied "right" interval for [1,4] and [3,4]. For [2,3], the interval [3,4] has minimum-"right" start point.
Approach #1:
/** * Definition for an interval. * struct Interval { * int start; * int end; * Interval() : start(0), end(0) {} * Interval(int s, int e) : start(s), end(e) {} * }; */ class Solution { public: vector<int> findRightInterval(vector<Interval>& intervals) { int len = intervals.size(); vector<int> ans; map<int, int> temp; for (int i = 0; i < len; ++i) { temp[intervals[i].start] = i; } for (int i = 0; i < len; ++i) { auto it = temp.lower_bound(intervals[i].end); if (it != temp.end()) ans.push_back(it->second); else ans.push_back(-1); } return ans; } };
Runtime: 64 ms, faster than 69.43% of C++ online submissions for Find Right Interval.
相关文章
- Leetcode: Find Right Interval
- 501. Find Mode in Binary Search Tree
- .Net Core 控制台程序错误:Can not find runtime target for framework '.NETCoreApp,Version=v1.0' compatible with one of the target runtimes: 'win10-x64, win81-x64, win8-x64, win7-x64'.
- 21Linux - 文件管理(查找文件:find)
- Linux Command find 查找匹配
- 完美解决 Could not find a version that satisfies the requirement 安装包名字 (from versions: )
- 非常简单的一个函数 竟然一直没有使用 find()
- 在执行脚本./scripts/get_maintainer.pl时报错"Can't locate File/Find.pm in @INC (you may need to install the File::Find module) (@INC contains:"如何处理?
- Error: could not find java.dll如何解决
- Android studio的错误:radle sync failed: Cause: failed to find target android-21 :
- 3.shell编程-文件查找之find命令
- 【LeetCode】162. Find Peak Element (3 solutions)
- 有用的 Mongo命令行 db.currentOp() db.collection.find().explain() - 摘自网络
- [LeetCode] 1304. Find N Unique Integers Sum up to Zero 和为零的N个唯一整数
- [LeetCode] Find Smallest Letter Greater Than Target 找比目标值大的最小字母
- [LeetCode] 436. Find Right Interval 找右区间
- qt.qpa.plugin: Could not find the Qt platform plugin "windows" in ""
- SpringBoot 多模块项目打包异常:Unable to find main class