Smart Intervals

Moderate
0/80
Average time to solve is 10m
8 upvotes
Asked in company
Ola

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

1
3
1 2
2 3
3 4

Sample output 1:

1 2 -1

Explanation of Sample output 1:

Smart interval for the interval [1, 2] is [2, 3] because the start point of [2, 3] is equal to the end point of [1, 2]. The index of [2, 3] is 1.
Smart interval for the interval [2, 3] is [3, 4] because the start point of [3, 4] is equal to the end point of [2, 3]. The index of [3, 4] is 2.
Smart interval for the interval [3, 4] does not exist. Hence, -1.
Therefore, the final answer is [1, 2, -1].

Sample Input2:

2
2
3 2
2 3
1 
1 1

Sample Output2:

1 0
0

Explanation of Sample output 2

Test Case 1:
Smart interval for the interval [3, 2] is [2, 3]. The index of [2, 3] is 1.
Smart interval for the interval [2, 3] is [3, 2]. The index of [3, 2] is 2. 
Hence, the answer is [1, 0]. 

Test Case 2: 
Do you really need an explanation?
Hint

Check for all the possibilities using brute force.

Approaches (3)
Brute force

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.
Time Complexity

O(N ^ 2), where N is the number of intervals. 

 

For each interval in the given intervals, we are iterating over all the intervals. Thus, the total time complexity is O(N) * O(N) = O(N ^ 2). 

Space Complexity

O(N), where N is the number of intervals.

 

O(N) space is used by the output array ‘result’.

Code Solution
(100% EXP penalty)
Smart Intervals
Full screen
Console