Find Right Interval Problem


Description

LeetCode Problem 436.

You are given an array of intervals, where intervals[i] = [start_i, end_i] and each start_i is unique.

The right interval for an interval i is an interval j such that start_j >= end_i and start_j is minimized.

Return an array of right interval indices for each interval i. If no right interval exists for interval i, then put -1 at index i.

Example 1:

1
2
3
Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.

Example 2:

1
2
3
4
5
Input: intervals = [[3,4],[2,3],[1,2]]
Output: [-1,0,1]
Explanation: There is no right interval for [3,4].
The right interval for [2,3] is [3,4] since start_0= 3 is the smallest start that is >= end_1= 3.
The right interval for [1,2] is [2,3] since start_1= 2 is the smallest start that is >= end_2= 2.

Example 3:

1
2
3
4
Input: intervals = [[1,4],[2,3],[3,4]]
Output: [-1,2,-1]
Explanation: There is no right interval for [1,4] and [3,4].
The right interval for [2,3] is [3,4] since start_2 = 3 is the smallest start that is >= end_1= 3.

Constraints:

  • 1 <=intervals.length <= 2 * 10^4
  • intervals[i].length == 2
  • -10^6 <= start_i <= end_i <= 10^6
  • The start pointof each interval is unique.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        map<int,int> m;
        m[INT_MAX] = -1;
        for (int i=0; i< intervals.size(); i++ ) {
            if (m.count(intervals[i][0])==0) {
                m[intervals[i][0]] = i;
            }
        }
        vector<int> ans;
        for (const auto& interval: intervals) {
            ans.push_back(m.lower_bound(interval[1])->second);
        }
        return ans;
    }
};




Related Posts

X Of A Kind In A Deck Of Cards Problem

LeetCode 914. In a deck of cards, each card has...

Word Subsets Problem

LeetCode 916. You are given two string arrays words1 and...

Vowel Spellchecker Problem

LeetCode 966. Given a wordlist, we want to implement a...

Verifying An Alien Dictionary Problem

LeetCode 953. In an alien language, surprisingly, they also use...

Unique Morse Code Words Problem

LeetCode 804. International Morse Code defines a standard encoding where...

Unique Email Addresses Problem

LeetCode 929. Every valid email consists of a local name...