FastPrep
Problem

Consolidate On-Call Rotations

Learn this problem
GoogleFULLTIMEOA
See Google hiring insights

Problem statement

You are given a list of on-call rotations. Each rotation has a name, start time, and end time, representing a half-open interval [start, end) during which that person is on call.

Produce the consolidated on-call timeline as maximal contiguous segments. In each output segment, the set of on-call people must remain constant throughout the entire interval. Sort segments by start time and omit gaps where nobody is on call.

Represent each input row as [name, start, end]. Return each output row as [start, end, names], where names is a comma-separated list of on-call names in lexicographic order.

Function

consolidateOnCallRotations(rotations: String[][]) → String[][]

Examples

Example 1

rotations = [["A", "10", "50"], ["B", "20", "60"], ["C", "30", "40"], ["D", "30", "40"]]return = [["10", "20", "A"], ["20", "30", "A,B"], ["30", "40", "A,B,C,D"], ["40", "50", "A,B"], ["50", "60", "B"]]

The original interview report presents this example as input and output tables.

Input rotations

namestartend
A1050
B2060
C3040
D3040

Consolidated schedule

startendnames
1020A
2030A, B
3040A, B, C, D
4050A, B
5060B

The active set changes at times 10, 20, 30, 40, 50, and 60.

Constraints

  • 1 <= rotations.length <= 2 * 10^5
  • Each row is [name, start, end].
  • 0 <= start < end <= 10^9
  • Multiple rotations may share the same start or end time.

More Google problems

drafts saved locally
public String[][] consolidateOnCallRotations(String[][] rotations) {
  // write your code here
}
rotations[["A", "10", "50"], ["B", "20", "60"], ["C", "30", "40"], ["D", "30", "40"]]
expected[["10", "20", "A", "20", "30", "A", "B", "30", "40", "A", "B", "C", "D", "40", "50", "A", "B", "50", "60", "B"]]
checking account