1229. Meeting Scheduler - Detailed Explanation

Problem Statement

Description:
You are given two lists (arrays) of time slots, where each time slot is represented as a pair of integers [start, end]. These time slots indicate when a person is available. You are also given an integer duration representing the length of the meeting you want to schedule.

Your task is to find the earliest time slot that works for both people, meaning the overlapping time between their availabilities must be at least duration long. If such a slot exists, return it as a pair [start, start + duration]; otherwise, return an empty list.

Example 1:

• Input:
  • slots1 = [[10, 50], [60, 120], [140, 210]]
  • slots2 = [[0, 15], [60, 70]]
  • duration = 8
• Output: [60, 68]
• Explanation:
  The first overlapping slot between the two schedules is between 60 and 70. Since the meeting duration is 8, the earliest valid meeting slot is from 60 to 68.

Example 2:

• Input:
  • slots1 = [[10, 50], [60, 120], [140, 210]]
  • slots2 = [[0, 15], [60, 70]]
  • duration = 12
• Output: []
• Explanation:
  Although there is an overlap between 60 and 70, its length (10) is less than the required 12, so no valid meeting slot exists.

Constraints:

• The time slots within each list are disjoint and may not be sorted.
• All time slots are in the format [start, end] with start < end.
• The meeting duration is a positive integer.

Hints

• Hint 1:
  The meeting can only happen in an interval where the two schedules overlap. Think about how to compute the intersection of two time intervals.

• Hint 2:
  Sorting the time slots based on their start times can make it easier to traverse both schedules simultaneously.

• Hint 3:
  Use a two-pointer approach to traverse both lists and check for overlaps. For each pair of slots from the two lists, determine the intersection and check if its length is at least duration.

Approach: Two-Pointer Technique After Sorting

Step-by-Step Process

1. Sort Both Lists:
   Although the lists may not be initially sorted, sort both slots1 and slots2 by their start times. This allows you to traverse the schedules in order.

2. Initialize Two Pointers:
   Use one pointer for each list (let’s call them i for slots1 and j for slots2).

3. Find Overlap for Each Pair:
   For the current time slots slot1 = [start1, end1] and slot2 = [start2, end2], compute the intersection:

   • The start of the overlap is max(start1, start2).
   • The end of the overlap is min(end1, end2).

   If min(end1, end2) - max(start1, start2) >= duration, then a valid meeting slot exists. The earliest meeting time will be [max(start1, start2), max(start1, start2) + duration].

4. Advance the Pointer:
   If there is no valid meeting slot for the current pair, advance the pointer of the interval that ends first (i.e. the one with the smaller end time) because it cannot possibly form an overlapping meeting with any later interval from the other list.

5. Return the Result:
   If you find a valid overlapping interval, return it immediately. If you finish scanning both lists without finding one, return an empty list.

Why This Works

• Sorting ensures that you always compare the earliest available time slots first.

• Using the two-pointer technique allows you to efficiently check overlapping intervals between the two schedules.

• By advancing the pointer with the earlier end time, you ensure that you are always looking for the next potential overlapping interval.

Code Implementation

Python Code