Merge Intervals by Type
Bloomberg LP● MediumNEW GRADPHONE SCREENProblem statement
You are given parallel arrays types and intervals. Row i represents one closed interval [start, end] belonging to types[i].
Merge overlapping intervals only when they have the same type. Intervals of different types never affect each other. For each type, sort by start and then end before merging; two closed intervals merge when the next start is at most the current end.
Return each merged interval as [type, start, end], with the numeric endpoints written as decimal strings. Emit type groups in the order each type first appears in types, and emit intervals within a group by ascending start.
Function
mergeIntervalsByType(types: String[], intervals: int[][]) → String[][]Examples
Example 1
types = ["A","B","A","A","B"]intervals = [[1,4],[2,3],[3,7],[10,12],[3,8]]return = [["A","1","7"],["A","10","12"],["B","2","8"]]The two overlapping A intervals form [1,7]; the later A interval stays separate. The B intervals touch at endpoint 3, so their closed ranges merge.
Example 2
types = ["X","Y","X"]intervals = [[5,5],[1,2],[1,3]]return = [["X","1","3"],["X","5","5"],["Y","1","2"]]X is emitted first because it appears first in types, even though the Y interval starts at the same value as X's earliest interval.
Example 3
types = []intervals = []return = []No input intervals produce no merged rows.
Constraints
0 <= types.length == intervals.length <= 100000.- Each type is a nonempty alphanumeric string of length at most
20. - Every interval has exactly two endpoints.
0 <= start <= end <= 1000000000.- The total output size is at most the input size.