# TreeMap<start, index>. O(n*logn)

• The idea is simple. For each interval's end we need to find higher or equal start. We can use tree map to store as a key intervals' starts and as a value will the index of the interval. Time complexity is O(n*logn)

``````public class Solution {
public int[] findRightInterval(Interval[] intervals) {
int n = intervals.length;
if (n==0) return new int[0];

TreeMap<Integer, Integer> starts = getStartsMap(intervals);

int rights[] = new int[n];
for (int i=0; i<n; i++) {
int end = intervals[i].end;
Map.Entry<Integer, Integer> entry = starts.ceilingEntry(end);
if (entry==null) rights[i]=-1;
else rights[i] = entry.getValue();
}

return rights;
}

public TreeMap<Integer, Integer> getStartsMap(Interval[] intervals) {
TreeMap<Integer, Integer> starts = new TreeMap<>();

for (int i=0; i<intervals.length; i++) {
starts.put(intervals[i].start, i);
}
return starts;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.