leetcode 436. Find Right Interval 最右边的区间+很棒的用Map统计遍历

Love The Way You Lie 2022-06-04 08:58 104阅读 0赞

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.

题意很简单，就是找到最靠近自己的右边的区间

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <cmath>
    
    using namespace std;
    
    /*
    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) 
        {
            map<int, int> hash;
            vector<int> res;
            int n = intervals.size();
            for (int i = 0; i < n; ++i)
                hash[intervals[i].start] = i;
    
            for (Interval in : intervals)
            {
                map<int,int>::iterator itr = hash.lower_bound(in.end);
                if (itr == hash.end()) 
                    res.push_back(-1);
                else 
                    res.push_back(itr->second);
            }
            return res;
        }
    };