Consolidate On-call Rotations into Maximal Constant Segments

You are given a list of on-call rotations. Each rotation is {name, start, end} representing a half-open interval [start, end) during which name is on-call. Produce the consolidated on-call timeline as a list of segments: Each output segment is a maximal contiguous time interval [s, e) such that the set of on-call people is constant throughout the interval. Segments must be sorted by start. Omit gaps where nobody is on-call. The names field represents the set of on-call people in that segment (order not required; you may output names in lexicographic order). Input Format The first line contains an integer n (number of rotations). Then follow n lines: name start end name is a string without spaces start, end are integers with start < end Output Format Output multiple lines, each: start end names where names is a comma-separated list of on-call people for that segment. Constraints 1 <= n <= 2 * 10^5 0 <= start, end <= 10^9 Intervals are half-open: [start, end) Multiple rotations may share the same start and/or end Example Input: A 10 50 B 20 60 C 30 40 D 30 40 Output: 10 20 A 20 30 A,B 30 40 A,B,C,D 40 50 A,B 50 60 B Example Input 4 A 10 50 B 20 60 C 30 40 D 30 40 Output 10 20 A 20 30 A,B 30 40 A,B,C,D 40 50 A,B 50 60 B