import java.util.*;

/*class Interval {
  int start = 0;
  int end = 0;

  Interval(int start, int end) {
    this.start = start;
    this.end = end;
  }
}*/

class Solution {

  public static int[] findNextInterval(Interval[] intervals) {

    Queue<Integer> minEndHeap = new PriorityQueue<>((i,j) -> intervals[i].end - intervals[j].end);
    Queue<Integer> minStartHeap = new PriorityQueue<>((i,j) -> intervals[i].start - intervals[j].start);

    int n = intervals.length;
    int[] result = new int[n];

    for (int i=0; i<n; i++) {
      minEndHeap.offer(i);
      minStartHeap.offer(i);
    }

     while(!minEndHeap.isEmpty()) {
     
      int endIdx = minEndHeap.poll();

      int endTime = intervals[endIdx].end;
      result[endIdx] = -1;

      while(!minStartHeap.isEmpty() &&
				     intervals[minStartHeap.peek()].start < endTime) {
        minStartHeap.poll();
      }

      if (!minStartHeap.isEmpty()) {
        result[endIdx] = minStartHeap.peek();
      }
     }
    
    return result;
  }
}