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.
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
1
3
1 2
2 3
3 4
1 2 -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].
2
2
3 2
2 3
1
1 1
1 0
0
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?
Check for all the possibilities using 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:
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).
O(N), where N is the number of intervals.
O(N) space is used by the output array ‘result’.
All tags
Sort by
Interview problems
Python || Smart Intervals
import bisect
def smartInterval(intervals, n):
ans = [-1] * n
start_times = sorted((intervals[i][0], i) for i in range(n))
for i in range(n):
current_end = intervals[i][1]
idx = bisect.bisect_left(start_times, (current_end,))
if idx < n:
ans[i] = start_times[idx][1]
return ans
Interview problems
Java Solution
import java.util.ArrayList;
public class Solution {
public static ArrayList<Integer> smartInterval(ArrayList<ArrayList<Integer>> intervals, int n) {
// Write your code here.
ArrayList<Integer> ans = new ArrayList<>();
for(int i=0;i<n;i++){
int currentEnd = intervals.get(i).get(1);
int index = -1;
int minDiff = Integer.MAX_VALUE;
for(int j=0;j<n;j++){
int currentStart = intervals.get(j).get(0);
if(currentEnd<=currentStart){
int diff = currentStart-currentEnd;
if(diff<minDiff){
minDiff = diff;
index = j;
}
}
}
ans.add(index);
}
return ans;
}
}
Interview problems
C++ Solution | 100 % Approach without Test Fail
/*
Time Complexity: O(N * log(N))
Space Complexity: O(N)
Where N is the number of intervals.
*/
#include<algorithm>
vector<int> smartInterval(vector<vector<int>> &intervals, int n)
{
// Create two array of pairs
vector<pair<int, int>>sortedStarts(n), sortedEnds(n);
for(int i = 0; i < n; i++)
{
sortedStarts[i] = {intervals[i][0], i};
sortedEnds[i] = {intervals[i][1], i};
}
// Sort the arrays
sort(sortedStarts.begin(), sortedStarts.end());
sort(sortedEnds.begin(), sortedEnds.end());
// Output array
vector<int>result(n, -1);
int i = 0, j = 0;
// Traverse through the arrays
while(i < n and j < n)
{
// Smart interval is found
if(sortedStarts[i].first >= sortedEnds[j].first)
{
int index = sortedEnds[j].second;
result[index] = sortedStarts[i].second;
j++;
}
else
{
i++;
}
}
return result;
}
Interview problems
Discussion thread on Interview Problem | Smart Intervals
Hey everyone, creating this thread to discuss the interview problem - Smart Intervals.
Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Smart Intervals
