Time:O(n\log n) Space:O(n) C++ 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; } }; JAVA 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; } }