Given an array arr[] of N intervals, the task is to calculate the index of the closest interval to the right of each of the given N intervals that do not overlap with the current interval.
Examples:
Input: arr[] = {{3, 4}, {2, 3}, {1, 2}}
Output: -1 0 1
Explanation: For the interval arr[0], there exists no interval to the right of it. For interval arr[1], i.e, [2, 3], the interval [3, 4] is the closest interval to its right that does not overlap it. Hence the required answer for arr[1] is 0. For the interval arr[2], both arr[1] and arr[2] are on its right side and does not overlap with arr[2], but arr[1] is the closest among them.Input: arr[] = {{1, 4}, {3, 4}, {2, 3}}
Output: -1 -1 1
Approach: The given problem can be solved using a greedy approach with the help of a binary search. The idea is to sort the intervals in increasing order of their starting points and find the closest interval to the right for each interval. Below are the steps to follow:
- Create a vector of pairs V storing the starting points and the index of each interval in arr[].
- Sort the vector V in increasing order of the starting points.
- Iterate through the array arr[] and for each index, find the index of the closest interval to the right such that it does not overlap with the current interval using the lower bound function.
Below is the implementation of the above approach:
C++
// C++ program of the above approach #include <bits/stdc++.h> using namespace std; // Function to find the index of closest // non overlapping interval to the right // of each of the given N intervals vector< int > closestInterval( vector<pair< int , int > > arr, int N) { // Vector to store starting value, // index pair of arr[] vector<pair< int , int > > V; // Loop to iterate arr[] for ( int i = 0; i < N; i++) { V.push_back({ arr[i].first, i }); } // Sort the vector V sort(V.begin(), V.end()); // Stores the resultant vector vector< int > res(N, -1); // Loop to iterate arr[] for ( int i = 0; i < N; i++) { // Calculate the closest // interval to the right auto it = lower_bound( V.begin(), V.end(), make_pair(arr[i].second, 0)); // If a valid interval // exist update res if (it != V.end()) { int idx = it - V.begin(); // Update res res[i] = V[idx].second; } } // Return Answer return res; } // Driver Code int main() { vector<pair< int , int > > arr{ { 1, 4 }, { 3, 4 }, { 2, 3 } }; for ( auto x : closestInterval(arr, arr.size())) { cout << x << " " ; } return 0; } |
Python3
# python3 program of the above approach import bisect # Function to find the index of closest # non overlapping interval to the right # of each of the given N intervals def closestInterval(arr, N): # Vector to store starting value, # index pair of arr[] V = [] # Loop to iterate arr[] for i in range ( 0 , N): V.append([arr[i][ 0 ], i]) # Sort the vector V V.sort() # Stores the resultant vector res = [ - 1 for _ in range (N)] # Loop to iterate arr[] for i in range ( 0 , N): # Calculate the closest # interval to the right it = bisect.bisect_left(V, [arr[i][ 1 ], 0 ]) # If a valid interval # exist update res if (it ! = len (V)): idx = it # Update res res[i] = V[idx][ 1 ] # Return Answer return res # Driver Code if __name__ = = "__main__" : arr = [[ 1 , 4 ], [ 3 , 4 ], [ 2 , 3 ]] for x in closestInterval(arr, len (arr)): print (x, end = " " ) # This code is contributed by rakeshsahni |
Java
/*package whatever //do not write package name here */ // java program of the above approach import java.util.*; import java.util.ArrayList; import java.util.Collections; public class GFG { // Function to find the index of closest // non overlapping interval to the right // of each of the given N intervals static List<Integer> closestInterval(List< int []> arr, int N) { // array to store starting value, // index pair of arr[] List< int []> V = new ArrayList<>(); for ( int i = 0 ; i < N; i++) { V.add( new int [] { arr.get(i)[ 0 ], i }); } // sort according to first element in the array Collections.sort( V, (a, b) -> Integer.compare(a[ 0 ], b[ 0 ])); // Stores the resultant vector List<Integer> res = new ArrayList<>(Collections.nCopies(N, - 1 )); for ( int i = 0 ; i < N; i++) { // Calculate the closest // interval to the right int [] curr = arr.get(i); int [] key = new int [] { curr[ 1 ], 0 }; // Calculate the closest // interval to the right int idx = Collections.binarySearch( V, key, (a, b) -> Integer.compare(a[ 0 ], b[ 0 ])); if (idx >= 0 ) { // Update res res.set(i, V.get(idx)[ 1 ]); } } return res; } public static void main(String[] args) { List< int []> arr = Arrays.asList( new int [] { 1 , 4 }, new int [] { 3 , 4 }, new int [] { 2 , 3 }); for ( int x : closestInterval(arr, arr.size())) { System.out.print(x + " " ); } } } |
Javascript
// JavaScript program const closestInterval = (arr, N) => { let V = [] for (let i = 0; i < N; i++) { V.push([arr[i][0], i]) } V.sort((a, b) => a[0] - b[0]) let res = Array(N).fill(-1) for (let i = 0; i < N; i++) { let curr = arr[i] let key = [curr[1], 0] let idx = V.findIndex((val) => val[0] >= key[0]) if (idx >= 0) { res[i] = V[idx][1] } } return res } let arr = [ [1, 4], [3, 4], [2, 3], ] console.log(closestInterval(arr, arr.length)) |
C#
using System; using System.Collections.Generic; class Program { static void Main( string [] args) { // Define the input array List<( int , int )> arr = new List<( int , int )> { (1, 4), (3, 4), (2, 3) }; // Call the ClosestInterval function to find the closest non-overlapping interval List< int > res = ClosestInterval(arr); // Print the resulting array foreach ( int x in res) { Console.Write(x + " " ); } } // Function to find the index of closest non-overlapping interval to the right of each of the given N intervals static List< int > ClosestInterval(List<( int , int )> arr) { // Vector to store starting value, index pair of arr[] List<( int , int )> V = new List<( int , int )>(); // Loop to iterate arr[] for ( int i = 0; i < arr.Count; i++) { V.Add((arr[i].Item1, i)); } // Sort the vector V V.Sort(); // Stores the resultant vector List< int > res = new List< int >(); // Loop to iterate arr[] for ( int i = 0; i < arr.Count; i++) { // Calculate the closest interval to the right // Binary search for the first element in V that is greater than or equal to (arr[i].Item2, 0) // If it exists, return its index in V // If it doesn't exist, return the bitwise complement of the index of the first element greater than (arr[i].Item2, 0) int idx = V.BinarySearch((arr[i].Item2, 0)); if (idx >= 0 && idx < V.Count) { // If a valid interval exists to the right, add its index to res res.Add(V[idx].Item2); } else if (idx == ~V.Count) { // If no valid interval exists to the right, add -1 to res res.Add(-1); } else { // If a valid interval exists to the right, add its index to res res.Add(V[~idx].Item2); } } // Return the resulting array return res; } } |
-1 -1 1
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!