Meeting Scheduler - Solution & Explanation

Problem Overview: You are given two lists of available time slots for two people and a required meeting duration. Each slot is represented as [start, end]. The task is to return the earliest time interval where both people are free for at least the required duration.

Approach 1: Brute Force Interval Comparison (O(n * m) time, O(1) space)

Check every slot from the first list against every slot from the second list. For each pair, compute the overlap using start = max(a_start, b_start) and end = min(a_end, b_end). If end - start >= duration, that overlap can host the meeting. This approach directly simulates the definition of overlapping intervals but requires comparing all pairs, which becomes slow when both lists are large.

Approach 2: Sorting + Two Pointers (O(n log n + m log m) time, O(1) space)

Sort both slot lists by start time, then scan them using two pointers. At each step, compare the current slots from both lists and compute their overlap. If the overlap duration is large enough, return the earliest valid interval. Otherwise, advance the pointer of the slot that ends earlier, since that slot cannot overlap with any later intervals. This technique leverages ordered intervals and reduces unnecessary comparisons, making it the optimal solution using sorting and the two pointers pattern on arrays.

Approach 3: Min Heap Merge (O((n + m) log(n + m)) time, O(n + m) space)

Push all slots from both participants into a min heap ordered by start time. Continuously pop the earliest interval and compare it with the next interval in the heap. If their overlap duration is at least the required meeting length, return the interval. This approach treats the problem like merging sorted intervals using a priority queue. It is slightly heavier in both memory and runtime but works well when intervals come from multiple sources.

Recommended for interviews: The sorting + two pointers approach is what interviewers typically expect. Brute force demonstrates that you understand how interval overlap works, but it does not scale. Sorting the slots and advancing the pointer with the earlier end time shows you recognize the key insight that overlapping windows can be scanned efficiently in linear time after ordering.