Intervals with Exactly One Person Online
Google● HardNEW GRADONSITE INTERVIEWProblem statement
You receive one online schedule for each person. schedules[p] contains that person's half-open intervals [start, end).
A person's own intervals may be unsorted, overlapping, or adjacent. Merge them first so that one person is never counted more than once at the same time.
Return every maximal non-empty half-open interval during which exactly one distinct person is online. Return the intervals in increasing start-time order. Adjacent ranges are merged whenever the number of online people remains exactly one across their shared boundary.
Function
exactlyOneOnline(schedules: int[][][]) → int[][]Examples
Example 1
schedules = [[[1,4],[6,8]],[[2,5]],[[7,9]]]return = [[1,2],[4,5],[6,7],[8,9]]Exactly one person is online before the first overlap, after the first overlap, before the second overlap, and after it.
Example 2
schedules = [[[1,5],[3,7]],[[6,8]]]return = [[1,6],[7,8]]The first person's intervals merge to [1,7). Both people are online on [6,7).
Constraints
0 <= schedules.length <= 100000.- The total number of intervals across all people is at most
200000. - Every interval contains two integers with
start < end. - Every endpoint is in
[-10^9, 10^9].