1. 題目

給定一組區間，對于每一個區間 i，檢查是否存在一個區間 j，它的起始點大于或等于區間 i 的終點，這可以稱為 j 在 i 的“右側”。

對于任何區間，你需要存儲的滿足條件的區間 j 的最小索引，這意味著區間 j 有最小的起始點可以使其成為“右側”區間。
如果區間 j 不存在，則將區間 i 存儲為 -1。
最后，你需要輸出一個值為存儲的區間值的數組。

注意: 你可以假設區間的終點總是大于它的起始點。 你可以假定這些區間都不具有相同的起始點。示例 1: 輸入: [ [1,2] ] 輸出: [-1] 解釋:集合中只有一個區間，所以輸出-1。示例 2: 輸入: [ [3,4], [2,3], [1,2] ] 輸出: [-1, 0, 1] 解釋:對于[3,4]，沒有滿足條件的“右側”區間。 對于[2,3]，區間[3,4]具有最小的“右”起點; 對于[1,2]，區間[2,3]具有最小的“右”起點。示例 3: 輸入: [ [1,4], [2,3], [3,4] ] 輸出: [-1, 2, -1] 解釋:對于區間[1,4]和[3,4]，沒有滿足條件的“右側”區間。 對于[2,3]，區間[3,4]有最小的“右”起點。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-right-interval
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 找每個區間的右端點，在所有左端點里的位置，找到大于等于右端點的第一個
• 利用 map 有序，key存儲左端點值，value存儲下標idx

class Solution { public:vector<int> findRightInterval(vector<vector<int>>& intervals) {map<int,int> m;//左端點，對應下標idxfor(int i = 0; i < intervals.size(); ++i)m[intervals[i][0]] = i;vector<int> ans(intervals.size());for(int i = 0; i < intervals.size(); ++i){auto it = m.lower_bound(intervals[i][1]);if(it == m.end())ans[i] = -1;elseans[i] = it->second;}return ans;} };

216 ms 23.3 MB

總結

以上是生活随笔為你收集整理的LeetCode 436. 寻找右区间（二分查找）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。