題目

• 你有一個區間數組intervals, 其中每個區間intervals[i]=[start, end]，而每個區間的start都是唯一的，不會重複數字。
• 要返回一個array，為每個區間*intervals[i]*的右區間的index，如果沒有則是-1。
• 右區間的定義
  • 區間intervals[i]與intervals[j]，其中start_j >= end_i 且start_j為最小值
• Example:
  • [[3,4],[2,3],[1,2]]
  • 返回 [-1, 0, 1]
    • [3,4]沒有右區間，所以為-1。
    • [2,3]的右區間為[3,4]，而[3,4]的index為0。
    • [1,2]的右區間為[2,3]，而[2,3]的index為1。

解法

• 基本思路:我們先以每個區間start去做排序，再以每個區間的end，去找符合右區間的規定。
• 如果直接將區間數組做排序，我們沒辦法得到原本每個區間的index，所以要先處理這個問題，因為要以每個區間的start去做排序，所以我們就先以start做為key，value做為index，儲存到hash table，用hash table是因為通常能有很好的搜索性能，這前面的題目有提過(應該)。
• 另外也建一個array，稱做starts，儲存每個區間start。
• 接著對starts排序
• 使用C++ STL提供的upper_bound，功能就如字面的意思，就是給定一個有序的範圍*[L,R]，並給予一個值val*，會返回在這範圍[L,R]中，第一個大於val的值的index。
• 那我們依序將val=每個區間的end,，並在排序好的starts找upper_bound，就會是 大於end的最小start(沒找到就直接給-1)，並拿去hash table中索引，就能找到原本的index，即我們要的答案。

Code

class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        vector<int> ans;
        vector<int> starts; 
        unordered_map<int,int> map; //hash table
        
        for(int i = 0; i< intervals.size(); i++){
            map[intervals[i][0]] = i; // key: start_i, value: i (index),
            starts.push_back(intervals[i][0]);  
        }
        
        sort(starts.begin(), starts.end());
        
        for(int i = 0; i< intervals.size(); i++){
            auto search_res = upper_bound(starts.begin(), starts.end(), intervals[i][1] - 1);
            if(search_res == starts.end()){
                ans.push_back(-1);
            } 
			else{ 
                ans.push_back(map[*search_res]);
            }
        }
		return ans;
    }
};

後來想到C++ STL中 map底層是用red-black tree實現的，所以使用它來儲存key-value pair會保持有序，與底層用hash table實現的unordered_map不同，所以本身也就有提供upper_bound與lower_bound。所以也附上來。
另外你問我結果怎看起來差不多，是因為我跑很多次取好看的哈哈，map理論上比較穩定O(lgn)，unordered_map則時快時慢，因為hash table有可能從O(1)變O(n)，但好像有點吃leetcode測資，map有時也會很慢，我猜是做了很大量的平衡。 反正那個數字就參考參考。

class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        vector<int> ans;
        map<int,int> map;
        
        for(int i = 0; i< intervals.size(); i++){
            map[intervals[i][0]] = i;
        }
        
        for(int i = 0; i< intervals.size(); i++){
            auto search_res = map.lower_bound(intervals[i][1]);
            if(search_res == map.end()){
                ans.push_back(-1);
            } 
			else{ 
                ans.push_back(search_res->second);
            }
        }
		return ans;
    }
};