FastPrepMaximum Compatible Time Windows

Maximum Compatible Time Windows

IBM logoIBM● MediumFULLTIMEOA
Learn

Problem statement

You are given two integer arrays, startTime and endTime, each of length n. Time window i begins at startTime[i], inclusive, and ends at endTime[i], exclusive.

Select as many pairwise non-overlapping time windows as possible and return the maximum number selected. Because each window is half-open, one selected window may end exactly when another selected window begins.

Function

selectMostCompatibleWindows(startTime: int[], endTime: int[]) → int

Examples

Example 1

startTime = [1,1,2]endTime = [3,2,4]return = 2

You may select window 0 by itself, or select windows 1 and 2. The latter two are compatible because window 1 ends exactly when window 2 begins.

Example 2

startTime = [1,1,2,3]endTime = [2,3,3,4]return = 3

Select windows 0, 2, and 3: [1,2), [2,3), and [3,4).

Example 3

startTime = [5,5,5]endTime = [8,7,6]return = 1

All three windows overlap, so at most one can be selected.

Constraints

  • 1 <= n <= 10^5.
  • 1 <= startTime[i], endTime[i] <= 10^9.
  • startTime[i] < endTime[i] for every time window.

More IBM problems

See IBM hiring insights
public int selectMostCompatibleWindows(int[] startTime, int[] endTime) {
  // write your code here
}
startTime[1,1,2]
endTime[3,2,4]
expected2
Checking account…