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.

Note:

  1. You may assume the interval's end point is always bigger than its start point.
  2. 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.


Solution

Approach #1 Brute Force [Time Limit Exceeded]

The simplest solution consists of picking up every interval in the set and looking for the the interval whose start point is larger(by a minimum difference) than the chosen interval's end point by scanning the complete set for every interval chosen. While scanning, we keep a track of the interval with the minimum start point satisfying the given criteria along with its index. The result obtained for every interval chosen is stored at the corresponding index in the res array which is returned at the end.

Complexity Analysis

  • Time complexity : . The complete set of intervals is scanned for every() interval chosen.
  • Space complexity : . array of size is used.

Approach #2 Using Sorting + Scanning [Time Limit Exceeded]

We make use of a hashmap , which stores the data in the form of a pair. Here, the corresponds to the interval chosen and the corresponds to the index of the particular interval in the given array. We store every element of the array in the -map.

Now, we sort the array based on the starting points. We needed to store the indices of the array in the hashmap, so as to be able to obtain the indices even after the sorting.

Now, we pick up every interval of the sorted array, and find out the interval from the remaining ones whose start point comes just after the end point of the interval chosen. How do we proceed? Say, we've picked up the interval right now. In order to find an interval satisfying the given criteria, we need not search in the intervals behind it. This is because the array has been sorted based on the starting points and the end point is always greater than the starting point for a given interval. Thus, we search in the intervals only with indices , such that . The first element encountered while scanning in the ascending order is the required result for the interval chosen, since all the intervals lying after this interval will have comparatively larger start points.

Then, we can obtain the index corresponding to the corresponding interval from the hashmap, which is stored in the corresponding entry of the array. If no interval satifies the criteria, we put a in the corresponding entry.

Complexity Analysis

  • Time complexity : .

Sorting takes time. For the first interval we need to search among elements. For the second interval, the search is done among elements and so on leading to a total of:

calculations.

  • Space complexity : . array of size is used. A hashmap of size is used.

Approach #3 Using Sorting + Binary Search [Accepted]

We can optimize the above approach to some extent, since we can make use of the factor of the array being sorted. Instead of searching for the required interval in a linear manner, we can make use of Binary Search to find an interval whose start point is just larger than the end point of the current interval.

Again, if such an interval is found, we obtain its index from the hashmap and store the result in the appropriate entry. If not, we put a at the corresponding entry.

Complexity Analysis

  • Time complexity : . Sorting takes time. Binary search takes n$$ intervals.

  • Space complexity : . array of size is used. A hashmap of size is used.

Approach #4 Using TreeMap [Accepted]

In this approach, instead of using a hashmap, we make use of a TreeMap , which is simply a Red-Black Tree(a kind of balanced Binary Search Tree) . This Treemap stores data in the form of pair and always remain sorted based on its keys. In our case, we store the data such that the start point of an interval acts as the and the index corresponding to the interval acts as the value, since we are concerned with data sorted based on the start points, as discussed in previous approaches. Every element of the array is stored in the TreeMap.

Now, we choose each element of the array and make use of a function TreeMap.ceilingEntry(end_point) to obtain the element in the TreeMap with its just larger than the of the currently chosen interval. The function ceilingEntry(Key) returns the element just with its larger than the Key(passed as the argument) from amongst the elements of the TreeMap and returns null if no such element exists.

If non-null value is returned, we obtain the from the pair obtained at the appropriate entry in the array. If a null value is returned, we simply store a at the corresponding entry.

Complexity Analysis

  • Time complexity : . Inserting an element into TreeMap takes time. such insertions are done. The search in TreeMap using ceilingEntry also takes time. such searches are done.

  • Space complexity : . array of size is used. TreeMap of size is used.

Approach #5 Using Two Arrays without Binary Search[Accepted]:

Algorithm

The intuition behind this approach is as follows: If we maintain two arrays,

  1. , which is sorted based on the start points.

  2. , which is sorted based on the end points.

Once we pick up the first interval(or, say the interval) from the array, we can determine the appropriate interval satisfying the right interval criteria by scanning the intervals in array from left towards the right, since the array is sorted based on the start points. Say, the index of the element chosen from the array happens to be .

Now, when we pick up the next interval(say the interval) from the array, we need not start scanning the array from the first index. Rather, we can start off directly from the index where we left off last time in the array. This is because end point corresponding to is larger than the one corresponding to and none of the intervals from , such that , satisfies the right neighbor criteria with , and hence not with as well.

If at any moment, we reach the end of the array i.e. and no element satisfying the right interval criteria is available in the array, we put a in the corresponding entry. The same holds for all the remaining elements of the array, whose end points are even larger than the previous interval encountered.

Also we make use of a hashmap initially to preserve the indices corresponding to the intervals even after sorting.

For more understanding see the below animation:

!?!../Documents/436_Find.json:1000,563!?!

Complexity Analysis

  • Time complexity : . Sorting takes time. A total of time is spent on searching for the appropriate intervals, since the and array is scanned only once.

  • Space complexity : . , and array of size are used. A hashmap of size is used.

Analysis written by: @vinod23

Submit Solution