Efficient Approach using binary search
The first step is same as the above approach. Sort the range intervals and then merge the overlapping intervals.
Now instead of searching linearly in merged ranges we can search using binary search if we store the prefix sum of number of elements in each range in a set.
For example: For the range { {1 4}, {6 8}, {9 10} } the number of elements in each range are : 4,3,2 respectively. Hence, prefix sum set would store {4 7 9}.
We can use the fact that the numbers are sorted to our advantage and use binary search to look for kth smallest element.
For kth smallest element we just have to find the lower_bound of k in set. the corresponding index will give us the index of the merged interval in which the required element is stored.
This works much faster for large number of queries and large N. Since the search time for each query is reduce to O(logn) from O(n).
Below is the implementation of the above approach :
C++
#include <bits/stdc++.h> using namespace std; vector<vector< int >> mergeIntervals(vector<vector< int >>&range){ int n=range.size(); vector<vector< int >>fin; for ( int i=0;i<n-1;i++){ if (range[i][1] >= range[i+1][0]){ range[i+1][0]=min(range[i][0],range[i+1][0]); range[i+1][1]=max(range[i][1],range[i+1][1]); } else { fin.push_back(range[i]); } } fin.push_back(range[n-1]); return fin; } vector< int >kthSmallestNum(vector<vector< int >>&range, vector< int >queries){ //sort the ranges sort(range.begin(),range.end()); //merge the overlapping intervals vector<vector< int >>merged=mergeIntervals(range); //set to store the cumulative sum of number of elements in each range //eg {1 4} {6 8} {9 10} would store {4 7 9} in set. set< int >s; int cumsum=0; for ( auto cur_range:merged){ int num_ele=cur_range[1]-cur_range[0]+1; cumsum+=num_ele; s.insert(cumsum); } //final vector to store the result of each query vector< int >fin; //for each query get the lower bound of required kth smallest element. // go to the index returned by lower_bound and get the required element for ( auto q:queries){ auto it=s.lower_bound(q); if (it==s.end())fin.push_back(-1); //if the required element is in first range else if (it==s.begin()){ fin.push_back(merged[0][0]+q-1); } //if the required element is in ith range. then discard previous range elements // if previous elements are prevele. then look for k=q-prevele in the current range else { int prevele=*prev(it); int kth=q-prevele; int idx=distance(s.begin(),it); fin.push_back(merged[idx][0]+kth-1); } } return fin; } // Driver\'s Function int main() { vector<vector< int >>range = {{1, 4}, {6, 8}}; int n =range.size(); vector< int >queries = {2, 6, 10}; int q = queries.size(); vector< int >ans=kthSmallestNum(range, queries); for ( auto it:ans) cout<<it<< " " ; return 0; } |
Java
import java.util.*; public class Main { public static List<Integer> kthSmallestNum(List<List<Integer>> range, List<Integer> queries) { //sort the ranges Collections.sort(range, Comparator.comparingInt(a -> a.get( 0 ))); //merge the overlapping intervals List<List<Integer>> merged = mergeIntervals(range); //set to store the cumulative sum of number of elements in each range //eg {1 4} {6 8} {9 10} would store {4 7 9} in set. NavigableSet<Integer> s = new TreeSet<>(); int cumsum = 0 ; for (List<Integer> cur_range : merged) { int num_ele = cur_range.get( 1 ) - cur_range.get( 0 ) + 1 ; cumsum += num_ele; s.add(cumsum); } //final vector to store the result of each query List<Integer> fin = new ArrayList<>(); //for each query get the lower bound of required kth smallest element. // go to the index returned by lower_bound and get the required element for ( int q : queries) { Integer tail = s.ceiling(q); if (tail == null ) { fin.add(- 1 ); //if the required element is in ith range. then discard previous range elements // if previous elements are prevele. then look for k=q-prevele in the current range } else { int idx = s.headSet(tail, true ).size() - 1 ; int prevele = idx == 0 ? 0 : s.headSet(tail, false ).last(); int kth = q - prevele; fin.add(merged.get(idx).get( 0 ) + kth - 1 ); } } return fin; } private static List<List<Integer>> mergeIntervals(List<List<Integer>> range) { int n = range.size(); List<List<Integer>> fin = new ArrayList<>(); for ( int i = 0 ; i < n - 1 ; i++) { if (range.get(i).get( 1 ) >= range.get(i + 1 ).get( 0 )) { range.get(i + 1 ).set( 0 , Math.min(range.get(i).get( 0 ), range.get(i + 1 ).get( 0 ))); range.get(i + 1 ).set( 1 , Math.max(range.get(i).get( 1 ), range.get(i + 1 ).get( 1 ))); } else { fin.add(range.get(i)); } } fin.add(range.get(n - 1 )); return fin; } // Driver\'s Function public static void main(String[] args) { List<List<Integer>> range = Arrays.asList(Arrays.asList( 1 , 4 ), Arrays.asList( 6 , 8 )); List<Integer> queries = Arrays.asList( 2 , 6 , 10 ); List<Integer> ans = kthSmallestNum(range, queries); for ( int it : ans) { System.out.print(it + " " ); } } } // This code is contributed by shivhack999 |
Python3
from bisect import bisect_left from typing import List def merge_intervals(intervals: List [ List [ int ]]) - > List [ List [ int ]]: n = len (intervals) fin = [] for i in range (n - 1 ): if intervals[i][ 1 ] > = intervals[i + 1 ][ 0 ]: intervals[i + 1 ][ 0 ] = min (intervals[i][ 0 ], intervals[i + 1 ][ 0 ]) intervals[i + 1 ][ 1 ] = max (intervals[i][ 1 ], intervals[i + 1 ][ 1 ]) else : fin.append(intervals[i]) fin.append(intervals[n - 1 ]) return fin def kth_smallest_num(intervals: List [ List [ int ]], queries: List [ int ]) - > List [ int ]: # sort the ranges intervals.sort() # merge the overlapping intervals merged = merge_intervals(intervals) # set to store the cumulative sum of number of elements in each range # eg {1 4} {6 8} {9 10} would store {4 7 9} in set. s = set () cumsum = 0 for cur_range in merged: num_ele = cur_range[ 1 ] - cur_range[ 0 ] + 1 cumsum + = num_ele s.add(cumsum) # final list to store the result of each query ans = [] # for each query get the lower bound of required kth smallest element. # go to the index returned by lower_bound and get the required element for q in queries: it = bisect_left( sorted (s), q) if it = = len (s): ans.append( - 1 ) elif it = = 0 : ans.append(merged[ 0 ][ 0 ] + q - 1 ) else : prevele = sorted (s)[it - 1 ] kth = q - prevele idx = sorted (s).index(prevele) ans.append(merged[idx + 1 ][ 0 ] + kth - 1 ) return ans # Driver's Function if __name__ = = '__main__' : intervals = [[ 1 , 4 ], [ 6 , 8 ]] queries = [ 2 , 6 , 10 ] ans = kth_smallest_num(intervals, queries) print (ans) |
Javascript
function mergeIntervals(range) { const n = range.length; const fin = []; for (let i = 0; i < n - 1; i++) { if (range[i][1] >= range[i + 1][0]) { range[i + 1][0] = Math.min(range[i][0], range[i + 1][0]); range[i + 1][1] = Math.max(range[i][1], range[i + 1][1]); } else { fin.push(range[i]); } } fin.push(range[n - 1]); return fin; } function kthSmallestNum(range, queries) { range.sort((a, b) => a[0] - b[0]); const merged = mergeIntervals(range); //set to store the cumulative sum of number of elements in each range //eg {1 4} {6 8} {9 10} would store {4 7 9} in set. const s = new Set(); let cumsum = 0; for (const cur_range of merged) { const num_ele = cur_range[1] - cur_range[0] + 1; cumsum += num_ele; s.add(cumsum); } //final vector to store the result of each query const fin = []; //for each query get the lower bound of required kth smallest element. // go to the index returned by lower_bound and get the required element for (const q of queries) { const it = s.values(); let tail = it.next().value; while (tail !== undefined && tail < q) { tail = it.next().value; } if (tail === undefined) { fin.push(-1); //if the required element is in ith range. then discard previous range elements // if previous elements are prevele. then look for k=q-prevele in the current range } else { const idx = Array.from(s.values()).indexOf(tail) - 1; const prevele = idx === -1 ? 0 : Array.from(s.values())[idx]; const kth = q - prevele; fin.push(merged[idx + 1][0] + kth - 1); } } return fin; } // Driver\'s Function const range = [[1, 4], [6, 8]]; const queries = [2, 6, 10]; const ans = kthSmallestNum(range, queries); console.log(ans.join( " " )); // This code is contributed by shiv1o43g |
C#
using System; using System.Collections.Generic; class Program { static List<List< int >> MergeIntervals(List<List< int >> intervals) { int n = intervals.Count; List<List< int >> fin = new List<List< int >>(); for ( int i = 0; i < n - 1; i++) { if (intervals[i][1] >= intervals[i + 1][0]) { intervals[i + 1][0] = Math.Min(intervals[i][0], intervals[i + 1][0]); intervals[i + 1][1] = Math.Max(intervals[i][1], intervals[i + 1][1]); } else { fin.Add(intervals[i]); } } fin.Add(intervals[n - 1]); return fin; } static List< int > KthSmallestNum(List<List< int >> intervals, List< int > queries) { // sort the ranges intervals.Sort((x, y) => x[0].CompareTo(y[0])); // merge the overlapping intervals List<List< int >> merged = MergeIntervals(intervals); // set to store the cumulative sum of number of elements in each range // eg {1 4} {6 8} {9 10} would store {4 7 9} in set. SortedSet< int > s = new SortedSet< int >(); int cumsum = 0; foreach (List< int > cur_range in merged) { int num_ele = cur_range[1] - cur_range[0] + 1; cumsum += num_ele; s.Add(cumsum); } // final list to store the result of each query List< int > ans = new List< int >(); // for each query get the lower bound of required kth smallest element. // go to the index returned by lower_bound and get the required element foreach ( int q in queries) { int [] sorted_s = new List< int >(s).ToArray(); int it = Array.BinarySearch(sorted_s, q); if (it < 0) { it = ~it; } if (it == s.Count) { ans.Add(-1); } else if (it == 0) { ans.Add(merged[0][0] + q - 1); } else { int prevele = sorted_s[it - 1]; int kth = q - prevele; int idx = new List< int >(s).IndexOf(prevele); ans.Add(merged[idx + 1][0] + kth - 1); } } return ans; } static void Main() { List<List< int >> intervals = new List<List< int >> { new List< int > { 1, 4 }, new List< int > { 6, 8 } }; List< int > queries = new List< int > { 2, 6, 10 }; List< int > ans = KthSmallestNum(intervals, queries); foreach ( int num in ans) { Console.Write(num + " " ); } } } |
2 7 -1
Time Complexity : O(nlog(n) + qlog(n))
Auxiliary Space: O(n)
Find k-th smallest element in given n ranges
Given n and q, i.e, the number of ranges and number of queries, find the kth smallest element for each query (assume k>1).Print the value of kth smallest element if it exists, else print -1.
Examples :
Input : arr[] = {{1, 4}, {6, 8}} queries[] = {2, 6, 10}; Output : 2 7 -1 After combining the given ranges, the numbers become 1 2 3 4 6 7 8. As here 2nd element is 2, so we print 2. As 6th element is 7, so we print 7 and as 10th element doesn't exist, so we print -1. Input : arr[] = {{2, 6}, {5, 7}} queries[] = {5, 8}; Output : 6 -1 After combining the given ranges, the numbers become 2 3 4 5 6 7. As here 5th element is 6, so we print 6 and as 8th element doesn't exist, so we print -1.
The idea is to first Prerequisite : Merge Overlapping Intervals and keep all intervals sorted in ascending order of start time. After merging in an array merged[], we use linear search to find kth smallest element.
Below is the implementation of the above approach :
C++
// C++ implementation to solve k queries // for given n ranges #include <bits/stdc++.h> using namespace std; // Structure to store the // start and end point struct Interval { int s; int e; }; // Comparison function for sorting bool comp(Interval a, Interval b) { return a.s < b.s; } // Function to find Kth smallest number in a vector // of merged intervals int kthSmallestNum(vector<Interval> merged, int k) { int n = merged.size(); // Traverse merged[] to find // Kth smallest element using Linear search. for ( int j = 0; j < n; j++) { if (k <= abs (merged[j].e - merged[j].s + 1)) return (merged[j].s + k - 1); k = k - abs (merged[j].e - merged[j].s + 1); } if (k) return -1; } // To combined both type of ranges, // overlapping as well as non-overlapping. void mergeIntervals(vector<Interval> &merged, Interval arr[], int n) { // Sorting intervals according to start // time sort(arr, arr + n, comp); // Merging all intervals into merged merged.push_back(arr[0]); for ( int i = 1; i < n; i++) { // To check if starting point of next // range is lying between the previous // range and ending point of next range // is greater than the Ending point // of previous range then update ending // point of previous range by ending // point of next range. Interval prev = merged.back(); Interval curr = arr[i]; if ((curr.s >= prev.s && curr.s <= prev.e) && (curr.e > prev.e)) merged.back().e = curr.e; else { // If starting point of next range // is greater than the ending point // of previous range then store next range // in merged[]. if (curr.s > prev.e) merged.push_back(curr); } } } // Driver\'s Function int main() { Interval arr[] = {{2, 6}, {4, 7}}; int n = sizeof (arr)/ sizeof (arr[0]); int query[] = {5, 8}; int q = sizeof (query)/ sizeof (query[0]); // Merge all intervals into merged[] vector<Interval>merged; mergeIntervals(merged, arr, n); // Processing all queries on merged // intervals for ( int i = 0; i < q; i++) cout << kthSmallestNum(merged, query[i]) << endl; return 0; } |
Java
// Java implementation to solve k queries // for given n ranges import java.util.*; class GFG { // Structure to store the // start and end point static class Interval { int s; int e; Interval( int a, int b) { s = a; e = b; } }; static class Sortby implements Comparator<Interval> { // Comparison function for sorting public int compare(Interval a, Interval b) { return a.s - b.s; } } // Function to find Kth smallest number in a Vector // of merged intervals static int kthSmallestNum(Vector<Interval> merged, int k) { int n = merged.size(); // Traverse merged.get( )o find // Kth smallest element using Linear search. for ( int j = 0 ; j < n; j++) { if (k <= Math.abs(merged.get(j).e - merged.get(j).s + 1 )) return (merged.get(j).s + k - 1 ); k = k - Math.abs(merged.get(j).e - merged.get(j).s + 1 ); } if (k != 0 ) return - 1 ; return 0 ; } // To combined both type of ranges, // overlapping as well as non-overlapping. static Vector<Interval> mergeIntervals(Vector<Interval> merged, Interval arr[], int n) { // Sorting intervals according to start // time Arrays.sort(arr, new Sortby()); // Merging all intervals into merged merged.add(arr[ 0 ]); for ( int i = 1 ; i < n; i++) { // To check if starting point of next // range is lying between the previous // range and ending point of next range // is greater than the Ending point // of previous range then update ending // point of previous range by ending // point of next range. Interval prev = merged.get(merged.size() - 1 ); Interval curr = arr[i]; if ((curr.s >= prev.s && curr.s <= prev.e) && (curr.e > prev.e)) merged.get(merged.size()- 1 ).e = curr.e; else { // If starting point of next range // is greater than the ending point // of previous range then store next range // in merged.get(.) if (curr.s > prev.e) merged.add(curr); } } return merged; } // Driver code public static void main(String args[]) { Interval arr[] = { new Interval( 2 , 6 ), new Interval( 4 , 7 )}; int n = arr.length; int query[] = { 5 , 8 }; int q = query.length; // Merge all intervals into merged.get()) Vector<Interval> merged = new Vector<Interval>(); merged=mergeIntervals(merged, arr, n); // Processing all queries on merged // intervals for ( int i = 0 ; i < q; i++) System.out.println( kthSmallestNum(merged, query[i])); } } // This code is contributed by Arnab Kundu |
Python3
# Python3 implementation to solve k queries # for given n ranges # Structure to store the # start and end point class Interval: def __init__( self , s, e): self .s = s self .e = e # Function to find Kth smallest number in a vector # of merged intervals def kthSmallestNum(merged: list , k: int ) - > int : n = len (merged) # Traverse merged[] to find # Kth smallest element using Linear search. for j in range (n): if k < = abs (merged[j].e - merged[j].s + 1 ): return merged[j].s + k - 1 k = k - abs (merged[j].e - merged[j].s + 1 ) if k: return - 1 # To combined both type of ranges, # overlapping as well as non-overlapping. def mergeIntervals(merged: list , arr: list , n: int ): # Sorting intervals according to start # time arr.sort(key = lambda a: a.s) # Merging all intervals into merged merged.append(arr[ 0 ]) for i in range ( 1 , n): # To check if starting point of next # range is lying between the previous # range and ending point of next range # is greater than the Ending point # of previous range then update ending # point of previous range by ending # point of next range. prev = merged[ - 1 ] curr = arr[i] if curr.s > = prev.s and curr.s < = prev.e and \ curr.e > prev.e: merged[ - 1 ].e = curr.e else : # If starting point of next range # is greater than the ending point # of previous range then store next range # in merged[]. if curr.s > prev.e: merged.append(curr) # Driver Code if __name__ = = "__main__" : arr = [Interval( 2 , 6 ), Interval( 4 , 7 )] n = len (arr) query = [ 5 , 8 ] q = len (query) # Merge all intervals into merged[] merged = [] mergeIntervals(merged, arr, n) # Processing all queries on merged # intervals for i in range (q): print (kthSmallestNum(merged, query[i])) # This code is contributed by # sanjeev2552 |
C#
// C# implementation to solve k queries // for given n ranges using System; using System.Collections; using System.Collections.Generic; class GFG{ // Structure to store the // start and end point public class Interval { public int s; public int e; public Interval( int a, int b) { s = a; e = b; } }; class sortHelper : IComparer { int IComparer.Compare( object a, object b) { Interval first = (Interval)a; Interval second = (Interval)b; return first.s - second.s; } } // Function to find Kth smallest number in // a Vector of merged intervals static int kthSmallestNum(ArrayList merged, int k) { int n = merged.Count; // Traverse merged.get( )o find // Kth smallest element using Linear search. for ( int j = 0; j < n; j++) { if (k <= Math.Abs(((Interval)merged[j]).e - ((Interval)merged[j]).s + 1)) return (((Interval)merged[j]).s + k - 1); k = k - Math.Abs(((Interval)merged[j]).e - ((Interval)merged[j]).s + 1); } if (k != 0) return -1; return 0; } // To combined both type of ranges, // overlapping as well as non-overlapping. static ArrayList mergeIntervals(ArrayList merged, Interval []arr, int n) { // Sorting intervals according to start // time Array.Sort(arr, new sortHelper()); // Merging all intervals into merged merged.Add((Interval)arr[0]); for ( int i = 1; i < n; i++) { // To check if starting point of next // range is lying between the previous // range and ending point of next range // is greater than the Ending point // of previous range then update ending // point of previous range by ending // point of next range. Interval prev = (Interval)merged[merged.Count - 1]; Interval curr = arr[i]; if ((curr.s >= prev.s && curr.s <= prev.e) && (curr.e > prev.e)) { ((Interval)merged[merged.Count - 1]).e = ((Interval)curr).e; } else { // If starting point of next range // is greater than the ending point // of previous range then store next range // in merged.get(.) if (curr.s > prev.e) merged.Add(curr); } } return merged; } // Driver code public static void Main( string []args) { Interval []arr = { new Interval(2, 6), new Interval(4, 7) }; int n = arr.Length; int []query = { 5, 8 }; int q = query.Length; // Merge all intervals into merged.get()) ArrayList merged = new ArrayList(); merged = mergeIntervals(merged, arr, n); // Processing all queries on merged // intervals for ( int i = 0; i < q; i++) Console.WriteLine(kthSmallestNum( merged, query[i])); } } // This code is contributed by pratham76 |
Javascript
<script> // JavaScript implementation to solve k queries // for given n ranges // Structure to store the // start and end point class Interval { constructor(a,b) { this .s=a; this .e=b; } } // Function to find Kth smallest number in a Vector // of merged intervals function kthSmallestNum(merged,k) { let n = merged.length; // Traverse merged.get( )o find // Kth smallest element using Linear search. for (let j = 0; j < n; j++) { if (k <= Math.abs(merged[j].e - merged[j].s + 1)) return (merged[j].s + k - 1); k = k - Math.abs(merged[j].e - merged[j].s + 1); } if (k != 0) return -1; return 0; } // To combined both type of ranges, // overlapping as well as non-overlapping. function mergeIntervals(merged,arr,n) { // Sorting intervals according to start // time arr.sort( function (a,b){ return a.s-b.s;}); // Merging all intervals into merged merged.push(arr[0]); for (let i = 1; i < n; i++) { // To check if starting point of next // range is lying between the previous // range and ending point of next range // is greater than the Ending point // of previous range then update ending // point of previous range by ending // point of next range. let prev = merged[merged.length - 1]; let curr = arr[i]; if ((curr.s >= prev.s && curr.s <= prev.e) && (curr.e > prev.e)) merged[merged.length-1].e = curr.e; else { // If starting point of next range // is greater than the ending point // of previous range then store next range // in merged.get(.) if (curr.s > prev.e) merged.push(curr); } } return merged; } // Driver code let arr=[ new Interval(2, 6), new Interval(4, 7)]; let n = arr.length; let query = [5, 8]; let q = query.length; // Merge all intervals into merged.get()) let merged = []; merged=mergeIntervals(merged, arr, n); // Processing all queries on merged // intervals for (let i = 0; i < q; i++) document.write( kthSmallestNum(merged, query[i])+ "<br>" ); // This code is contributed by avanitrachhadiya2155 </script> |
6 -1
Time Complexity : O(nlog(n) + qn)
Auxiliary Space: O(n)