FastPrep
Problem · Intervals

Streaming Interval Peak Concurrency

Learn this problem
● HardUber logoUberFULLTIMEONSITE INTERVIEW
See Uber hiring insights

Problem statement

Meeting intervals arrive one at a time in the given order. After every insertion, return the highest concurrency observed anywhere in the timeline so far.

  • Intervals are half-open: [start, end).
  • An interval ending at time t does not overlap one starting at t.
  • The intervals are not sorted in advance.

Return one integer per arrival.

Function

peakConcurrencyAfterEachInsert(intervals: int[][]) → int[]

Examples

Example 1

intervals = [[1,5],[2,4],[5,7],[3,6]]return = [1,2,2,3]

The fourth insertion makes three intervals overlap during [3,4). The endpoint at 5 is handled as an end before a start.

Example 2

intervals = [[10,20],[0,10],[20,30]]return = [1,1,1]

The three intervals only touch at endpoints, so the peak remains one.

Constraints

  • intervals is non-empty.
  • Every row is [start, end] with start < end.
  • Coordinates are signed integers.

More Uber problems

drafts saved locally
public int[] peakConcurrencyAfterEachInsert(int[][] intervals) {
    // TODO: return the all-time peak after every half-open interval insertion.
}
intervals[[1,5],[2,4],[5,7],[3,6]]
expected[1,2,2,3]
checking account