Show problems as
Classic problem #1229MediumArrayTwo PointersSorting

Meeting Scheduler

Real-world version: Earliest Window Both Are Free
Tracked in this browser only
Read Meeting Scheduler on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Two people's free periods are given as slots1 and slots2, each entry a pair [start, end] meaning free from start up to end. A person's own periods never overlap each other.

Find the earliest moment t at which both are free for a stretch of duration, that is where the whole of t to t + duration lies inside one period of each.

Return [t, t + duration], or an empty list when no such moment exists.

Examples

Example 1

Input
slots1 = [[14, 27], [40, 55], [70, 90]], slots2 = [[20, 33], [50, 60], [80, 95]], duration = 8
Output
[80, 88]

The first overlap runs from 20 to 27, only seven long. The next runs from 50 to 55, five long. The one from 80 to 90 is ten long, so the stretch starts at 80.

Example 2

Input
slots1 = [[0, 5]], slots2 = [[5, 10]], duration = 1
Output
[]

The two periods meet at a single moment and overlap over nothing, so there is no room even for a stretch of one.

Example 3

Input
slots1 = [[10, 20], [0, 5]], slots2 = [[0, 30]], duration = 5
Output
[0, 5]

The periods are not given in order, and sorting them first shows the earliest workable overlap starts at 0.

Constraints

  • 1 <= slots1.length <= 10^4
  • 1 <= slots2.length <= 10^4
  • slots1[i].length == 2
  • slots2[i].length == 2
  • slots1[i][0] < slots1[i][1]
  • slots2[i][0] < slots2[i][1]
  • 0 <= slots1[i][j] <= 10^9
  • 0 <= slots2[i][j] <= 10^9
  • 1 <= duration <= 10^6
  • Neither person's own periods overlap each other

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_available_duration(slots1: list[list[int]], slots2: list[list[int]], duration: int) -> list[int]:
Java
public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration)

More on the same topics