Skip to content

436. Find Right Interval 👍

  • Time: $O(n\log n)$
  • Space: $O(n)$
 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) {
    vector<int> ans;
    map<int, int> startToIndex;

    for (int i = 0; i < intervals.size(); ++i)
      startToIndex[intervals[i][0]] = i;

    for (const vector<int>& interval : intervals) {
      const auto it = startToIndex.lower_bound(interval[1]);
      ans.push_back(it == startToIndex.cend() ? -1 : it->second);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public int[] findRightInterval(int[][] intervals) {
    final int n = intervals.length;

    int[] ans = new int[n];
    TreeMap<Integer, Integer> startToIndex = new TreeMap<>();

    for (int i = 0; i < n; ++i)
      startToIndex.put(intervals[i][0], i);

    for (int i = 0; i < n; ++i) {
      Map.Entry<Integer, Integer> entry = startToIndex.ceilingEntry(intervals[i][1]);
      ans[i] = entry == null ? -1 : entry.getValue();
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
from sortedcontainers import SortedDict


class Solution:
  def findRightInterval(self, intervals: list[list[int]]) -> list[int]:
    ans = []
    startToIndex = SortedDict()

    for i, (start, end) in enumerate(intervals):
      startToIndex[start] = i

    for start, end in intervals:
      i = startToIndex.bisect_left(end)
      ans.append(-1 if i == len(startToIndex) else startToIndex.peekitem(i)[1])

    return ans