Find Right Interval

LeetCode Q 436 - Find Right Interval

Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the “right” of i.
For any interval i, you need to store the minimum interval j’s index, which means that the interval j has the minimum start point to build the “right” relationship for interval i. If the interval j doesn’t exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.

Solution

Code:

private Comparator<int[]> comparator = new Comparatro<int[]>() {
	public int compare(int[] a, int[] b) {
		if (a[1] != b[1]) return a[1] - b[1]; // order the pos in ascending order
		if (a[2] == 1) return 1;// start point comes first
		return -1;
	}
}

public int[] findRightInterval(int[][] intervals) {
	int[] res = new int[intervals.length];
	List<int[]> points = new ArrayList<>();

	// we store the left point and right point of the interval seperately, and use an array to wrap it.
	// int[0]: index; int[1]: left / right pos; int[2]: an indecator, 1 - left point, -1 - right point.
	for (int i = 0; i < intervals.length; i++) {
		points.add(new int[] {i, intervals[i][0], 1}); // left point
		points.add(new int[] {i, intervals[i][0], 1}); // right point
	}

	Collections.sort(points, comparator);

	Queue<int[]> pq = PriorityQueue<>(comparator);

	for (int i = points.size() - 1; i >= 0; i--) {
		int[] point = points.get(i);
		if (point[2] == 1) {// it's a left point
			pq.offer(point);
		} else {
			if (pq.size() == 0) // no right point
				res[point[0]] = -1;
			else // find the smallest right point
				res[point[0]] = pq.peek()[0];
		}
	}

	return res;
}