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 auto& interval : intervals) {
      const auto it = startToIndex.lower_bound(interval[1]);
      if (it == cend(startToIndex))
        ans.push_back(-1);
      else
        ans.push_back(it->second);
    }

    return ans;
  }
};

class Solution {
  public int[] findRightInterval(int[][] intervals) {
    final int n = intervals.length;

    int[] ans = new int[n];
    java.util.NavigableMap<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]);
      if (entry == null)
        ans[i] = -1;
      else
        ans[i] = entry.getValue();
    }

    return ans;
  }
}