436. Find Right Interval #

Problem #

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.

Note:

You may assume the interval’s end point is always bigger than its start point.
You may assume none of these intervals have the same start point.

Example 1:

Input: [ [1,2] ]

Output: [-1]

Explanation: There is only one interval in the collection, so it outputs -1.

Example 2:

Input: [ [3,4], [2,3], [1,2] ]

Output: [-1, 0, 1]

Explanation: There is no satisfied "right" interval for [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point;
For [1,2], the interval [2,3] has minimum-"right" start point.

Example 3:

Input: [ [1,4], [2,3], [3,4] ]

Output: [-1, 2, -1]

Explanation: There is no satisfied "right" interval for [1,4] and [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point.

Note: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Problem Summary #

Given a set of intervals, for each interval i, check whether there exists an interval j whose start point is greater than or equal to the end point of interval i; this can be called j being on the “right” side of i.

For any interval, you need to store the minimum index of the interval j that satisfies the condition, which means interval j has the minimum start point that can make it a “right” interval. If interval j does not exist, store -1 for interval i. Finally, you need to output an array whose values are the stored interval values.

Note:

You may assume the interval’s end point is always greater than its start point.
You may assume none of these intervals have the same start point.

Solution Ideas #

Given an array of interval, find the index of the first interval to the right of each interval. Interval A is to the right of interval B: the value of the left boundary of interval A is greater than or equal to the value of the right boundary of interval B.
This problem can obviously be solved with binary search. First sort the interval array, then for each interval, use binary search to find the interval whose value is greater than or equal to the right boundary value of the interval. If found, store the index in the final array; if not found, store -1 in the final array.

Code #


package leetcode

import "sort"

// Solution 1: Use built-in sort + binary search
func findRightInterval(intervals [][]int) []int {
	intervalList := make(intervalList, len(intervals))
	// Convert to interval type
	for i, v := range intervals {
		intervalList[i] = interval{interval: v, index: i}
	}
	sort.Sort(intervalList)
	out := make([]int, len(intervalList))
	for i := 0; i < len(intervalList); i++ {
		index := sort.Search(len(intervalList), func(p int) bool { return intervalList[p].interval[0] >= intervalList[i].interval[1] })
		if index == len(intervalList) {
			out[intervalList[i].index] = -1
		} else {
			out[intervalList[i].index] = intervalList[index].index
		}
	}
	return out
}

type interval struct {
	interval []int
	index    int
}

type intervalList []interval

func (in intervalList) Len() int { return len(in) }
func (in intervalList) Less(i, j int) bool {
	return in[i].interval[0] <= in[j].interval[0]
}
func (in intervalList) Swap(i, j int) { in[i], in[j] = in[j], in[i] }

// Solution 2: Implement sort manually + binary search
func findRightInterval1(intervals [][]int) []int {
	if len(intervals) == 0 {
		return []int{}
	}
	intervalsList, res, intervalMap := []Interval{}, []int{}, map[Interval]int{}
	for k, v := range intervals {
		intervalsList = append(intervalsList, Interval{Start: v[0], End: v[1]})
		intervalMap[Interval{Start: v[0], End: v[1]}] = k
	}
	quickSort(intervalsList, 0, len(intervalsList)-1)
	for _, v := range intervals {
		tmp := searchFirstGreaterInterval(intervalsList, v[1])
		if tmp > 0 {
			tmp = intervalMap[intervalsList[tmp]]
		}
		res = append(res, tmp)
	}
	return res
}

func searchFirstGreaterInterval(nums []Interval, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + ((high - low) >> 1)
		if nums[mid].Start >= target {
			if (mid == 0) || (nums[mid-1].Start < target) { // Find the first element greater than or equal to target
				return mid
			}
			high = mid - 1
		} else {
			low = mid + 1
		}
	}
	return -1
}