# Alternative solution (sort twice)

• Sort the intervals twice:
byStart -> sort by start
byEnd -> sort by end
end for each interval in byEnd we check byStart.
If start >= end then we record the index.
else we advance the byStart index.

``````class Solution {
public int[] findRightInterval(Interval[] intervals) {
Map<Integer, Integer> startToIndex = new HashMap<>();
for (int i=0; i<intervals.length; i++) {
startToIndex.put(intervals[i].start, i);
}
Interval[] byStart = Arrays.copyOf(intervals, intervals.length);
Arrays.sort(byStart, (i1, i2) -> i1.start - i2.start);
Interval[] byEnd = Arrays.copyOf(intervals, intervals.length);
Arrays.sort(byEnd, (i1, i2) -> i1.end - i2.end);
int[] result = new int[intervals.length];
int index = 0;
for (int i=0; i<byEnd.length; i++) {
while (index < byStart.length && byStart[index].start < byEnd[i].end) {
index++;
}
if (index < byStart.length) {
result[startToIndex.get(byEnd[i].start)] = startToIndex.get(byStart[index].start);
} else {
result[startToIndex.get(byEnd[i].start)] = -1;
}
}
return result;
}
}
``````

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