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

Find Duplicate Subtrees Problem

LeetCode 652. Given the rootof a binary tree, return all...

Delete And Earn Problem

LeetCode 740. You are given an integer array nums. You...

Degree Of An Array Problem

LeetCode 697. Given a non-empty array of non-negative integers nums,...

Custom Sort String Problem

LeetCode 791. You are given two strings order and s....

Basic Calculator IV Problem

LeetCode 770. Given an expression such as expression = “e...

Sort Characters By Frequency Problem

LeetCode 451. Given a string s, sort it in decreasing...