Difficulty: Medium
Problem Link: https://leetcode.com/problems/find-right-interval/

Problem

Find Right Interval LeetCode OJ.png

Tag: Binary Search

Explanation

• 這道題的所用的算法就是二分查找，關(guān)鍵在于在算法的哪一部分使用二分查找以及如何使用二分查找。
• 先要注意到兩個條件洛波，(1) 區(qū)間的end point 大于 start point (2) 不存在兩個具有相同的start point 的區(qū)間
• 我們要尋找的是intervals[i] (區(qū)間i)的最小的 right interval, 稱之為targetInterval掂之，即這個區(qū)間targetInterval的start point 要大于等于 intervals[i]的end point主儡，而且在所有滿足以上條件的區(qū)間中独旷，start point必須是最小的余赢。所以可以想到要將intervals按照start point來進(jìn)行排序构眯，這樣就可以通過lgn的時間復(fù)雜度找到targetInterval愕难。考慮到最終的返回結(jié)果中要返回的intervals在原序列中的index惫霸，所以在排序之前猫缭，先將原序列進(jìn)行保存。
• 我的算法實現(xiàn)中保存了兩個關(guān)于原數(shù)組的數(shù)據(jù)體壹店，第一個是應(yīng)用哈希表映射了start point和index的關(guān)系猜丹，以確保在通過二分查找到了targetInterval的start point之后，可以在O(1)的時間復(fù)雜度里找到原序列中的i硅卢。第二個是完全復(fù)制了原數(shù)組射窒，返回結(jié)果中是按照原序列排序的，在排序之前需要先拷貝一份将塑。
• 二分查找的思路很簡單轮洋，不斷地二分比較mid值(mid = (l + r) >> 1)是否符合條件，直至l和r相等抬旺，最后輸出結(jié)果到結(jié)果數(shù)組中去弊予。

cpp solution

/**
 * 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) {
        unordered_map<int, int> map;
        for (int i = 0; i < intervals.size(); i++) {
            map[intervals[i].start] = i;
        }
        
        auto comp = [](Interval x, Interval y) {
            return x.start < y.start;
        };
        
        vector<Interval> originIntervals;
        for (auto x : intervals) {
            originIntervals.push_back(x);
        }
        
        sort(intervals.begin(), intervals.end(), comp);
        
        vector<int> res;
        for (auto it : originIntervals) {
            int searchInt = it.end;
            
            int l = 0, r = intervals.size() - 1;
            
            while (l < r) {
                int mid = (l + r) >> 1;
                if (searchInt > intervals[mid].start) {
                   l = mid + 1;
                } else {
                   r = mid;
                }
            }
            
            if (searchInt > intervals[l].start) {
                res.push_back(-1);
            } else {
                res.push_back(map[intervals[l].start]);
            }
        }
        
        return res;
    }
};