Find k | Structure to store the start and end point ; Function to find Kth smallest number in a vector of merged intervals ; Traverse merged [ ] to find Kth smallest element using Linear search . ; To combined both type of ranges , overlapping as well as non - overlapping . ; Sorting intervals according to start time ; Merging all intervals into merged ; 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 . ; If starting point of next range is greater than the ending point of previous range then store next range in merged [ ] . ; Driver Code ; Merge all intervals into merged [ ] ; Processing all queries on merged intervals
class Interval : NEW_LINE INDENT def __init__ ( self , s , e ) : NEW_LINE INDENT self . s = s NEW_LINE self . e = e NEW_LINE DEDENT DEDENT def kthSmallestNum ( merged : list , k : int ) -> int : NEW_LINE INDENT n = len ( merged ) NEW_LINE for j in range ( n ) : NEW_LINE INDENT if k <= abs ( merged [ j ] . e - merged [ j ] . s + 1 ) : NEW_LINE INDENT return merged [ j ] . s + k - 1 NEW_LINE DEDENT k = k - abs ( merged [ j ] . e - merged [ j ] . s + 1 ) NEW_LINE DEDENT if k : NEW_LINE INDENT return - 1 NEW_LINE DEDENT DEDENT def mergeIntervals ( merged : list , arr : list , n : int ) : NEW_LINE INDENT arr . sort ( key = lambda a : a . s ) NEW_LINE merged . append ( arr [ 0 ] ) NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT prev = merged [ - 1 ] NEW_LINE curr = arr [ i ] NEW_LINE if curr . s >= prev . s and curr . s <= prev . e and curr . e > prev . e : NEW_LINE INDENT merged [ - 1 ] . e = curr . e NEW_LINE DEDENT else : NEW_LINE INDENT if curr . s > prev . e : NEW_LINE INDENT merged . append ( curr ) NEW_LINE DEDENT DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ Interval ( 2 , 6 ) , Interval ( 4 , 7 ) ] NEW_LINE n = len ( arr ) NEW_LINE query = [ 5 , 8 ] NEW_LINE q = len ( query ) NEW_LINE merged = [ ] NEW_LINE mergeIntervals ( merged , arr , n ) NEW_LINE for i in range ( q ) : NEW_LINE INDENT print ( kthSmallestNum ( merged , query [ i ] ) ) NEW_LINE DEDENT DEDENT