Last Updated: 11 Jan, 2021

Smart Intervals

Moderate

Asked in company

Problem statement

You are given an array of intervals, where intervals[i] = [start(i), end(i)] and each start(i) is unique.

The smart interval for an interval ‘i’ is an interval ‘j’ such that start(j) is greater than or equal to end(i) and start(j) should be minimum.

Your task is to return an array of smart interval indices for each interval. If no smart interval exists for an interval ‘i’, then place -1 at index ‘i’ in the output array.

Input Format:

The first line contains a single integer T representing the number of test cases.

The first line of the test case contains an integer ‘N’ denoting the number of intervals.

Each of the following ‘N’ lines contains 2 space-separated integers denoting the start and end of an interval.

Output Format :

The first and only line of output contains ‘N’ space-separated integers as described above.

The output of every test case is printed in a separate line.

Note :

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 10^4
1 <= start, end <= 10^4

Time Limit : 1sec

Solve now

Approaches

01 Approach

The idea is to check all the intervals for a particular interval and store the index of the smart interval for the current interval. This can be done using two nested loops.

Algorithm:

Initialise an output array ‘result’ of size ‘N’ by -1.
Iterate over all the intervals using a for loop. For the current interval ‘i’:
- Initialise an integer ‘smartIndex’ by -1.
- Iterate over all the intervals using a variable ‘j’.
  - If ‘i’ and ‘j’ are different, compare the interval ‘i’ and interval ‘j’.
    - Update ‘smartIndex’ by the minimum j whose start point is greater than the end point of interval ‘i’.
- Update the result[i] by smartIndex.
Return the final ‘result’ array.

Solve now

02 Approach

Observe one thing that any interval can be the smart interval for any other interval, if it satisfies the constraints.

Now, if we sort the given array, we can apply binary search and for each interval ‘i’, we can just find the first interval with a starting point greater than equal to the ending point of ‘i’. If such an interval exists, it will be the smart interval for the interval ‘i’.

Algorithm:

To keep track of the indices of intervals in the original array, append the index of each interval in the interval itself.
Now, interval[i] = [ start, end, index].
Sort the array in ascending order of the first element, i.e start point.
Create an output integer array ‘result’ of size ‘N’.
Now, traverse the intervals array using a variable i:
- Try to find the smart interval for each interval by applying binary search on the given array.
  - For the current interval, if the smart interval exists, update its index in the result array for result[i].
  - Else, update result[i] as -1.
Finally, return the output array ‘result’.

Solve now

03 Approach

The idea is to create two different arrays, one sorted according to start points and second is sorted according to the end points. Then we will simply traverse these arrays, and without using binary search we will find the smart interval for each interval, if it exists.

Let’s walk through the algorithm for better understanding:

Algorithm:

Create an array of pairs ‘sortedStarts’ where the first element of the pair is the ‘start’ point of each interval and the second element is the index of the interval.
Create another array of pairs ‘sortedEnds’ where the first element of the pair is the ‘end’ point of each interval and the second element is the index of the interval.
Sort the ‘sortedStarts’ and ‘sortedEnds’ in ascending order of the first element.
Create an output integer array ‘result’ of size ‘N’.
Now, simply traverse ‘sortedStarts’ and ‘sortedEnds’ using two pointers, i and j (i for ‘sortedStarts’ and ‘j’ for ‘sortedEnds’, both initialized to 0 initially):
- If the first element of sortedStarts[i] is greater than or equal to the first element of sortedEnds[j], we will update the result for the second element of ‘sortedEnds[j]’ by the second element of the ‘sortedStarts[i]’ as it is the smart interval with minimum start point value.
  Increment j by 1.
- Else, increment i by 1.
Finally, return the output array ‘result’.

Consider an example:

Intervals = [[3, 4], [2, 3], [5,1]]

Initially,

sortedStarts = [(3, 0), (2, 1), (5, 2)]

sortedEnds = [(4, 0), (3, 1), (1, 2)]

Now sort these arrays. After sorting,

sortedStarts = [(2, 1), (3, 0), (5, 2)]

sortedEnds = [(1, 2), (3, 1), (4, 0)]

Initialise i = 0, j = 0.

stortedEnds[j].first = 1

sortedStarts[i].first = 2

2 is greater than equal to one, therefore we have found the smart interval for this interval. Now update result[sortedEnds[j].second] = sortedStarts[i].second i.e. result[2] = 1.

Increment j to find the smart interval for the next interval.

Now, i = 0, j = 1

stortedEnds[j].first = 3

sortedStarts[i].first = 2

2 is smaller than 3, but we want the start point of the smart interval to be greater than or equal to the end point of the interval.

Thus, increment i.

Now, i = 1, j = 1.

stortedEnds[j].first = 3

sortedStarts[i].first = 3

3 is greater than equal to three, therefore we have found the smart interval for this interval. Now update result[sortedEnds[j].second] = sortedStarts[i].second. iI.e. result[1] = 0

Increment j to find the smart interval for the next interval.

Now, i = 1, j = 2

stortedEnds[j].first = 4

sortedStarts[i].first = 3

3 is smaller than 4, but we want the start point of the smart interval to be greater than or equal to the end point of the interval.

Thus, increment i.

Now, i = 2, j = 2.

stortedEnds[j].first = 4

sortedStarts[i].first = 5

5 is greater than equal to three, therefore we have found the smart interval for this interval. Now update result[sortedEnds[j].second] = sortedStarts[i].second. i.e. result[0] = 2

As all the intervals are covered, the loop will end.

The final result array is [2, 0, 1].

Solve now