Problem Description

You are given two arrays slots1 and slots2 that represent the available time slots for two people, and an integer duration representing the length of a meeting they need to schedule.

Each time slot is represented as an array [start, end], where start and end are inclusive boundaries (meaning the person is available from time start to time end, including both endpoints).

Your task is to find the earliest time slot where both people are available for at least duration minutes. If such a common time slot exists, return an array [meetingStart, meetingEnd] where the meeting would start at meetingStart and end at meetingStart + duration. If no such time slot exists, return an empty array [].

Key constraints:

• Within each person's schedule, time slots don't overlap (they are non-intersecting)
• For any two slots [start1, end1] and [start2, end2] of the same person, either start1 > end2 or start2 > end1

For example:

• If person 1 has slots [[10, 50], [60, 120]]
• And person 2 has slots [[0, 15], [45, 70]]
• With duration = 8
• The earliest common available time would be [45, 53] (both are free from 45 to 50, which gives us at least 8 minutes)

The solution uses a two-pointer approach after sorting both arrays. It finds overlapping intervals between the two schedules and checks if the overlap is long enough to accommodate the required duration. The pointers advance based on which person's current slot ends earlier, ensuring we examine all possible overlapping intervals in chronological order.

Intuition

To find when both people can meet, we need to identify time periods where both are available simultaneously. This is essentially finding the intersection of two sets of time intervals.

The key insight is that we want the earliest possible meeting time. This naturally suggests processing the time slots in chronological order. By sorting both arrays first, we can examine potential meeting times from earliest to latest.

Once sorted, we can use two pointers to efficiently find overlapping intervals. For any pair of intervals (one from each person), the overlap exists from max(start1, start2) to min(end1, end2). If this overlap has length ≥ duration, we've found our answer.

Why two pointers? Consider what happens after checking two intervals:

• If person 1's interval ends before person 2's, there's no point checking person 1's current interval against any later intervals of person 2 (they'll start even later)
• We should move to person 1's next interval instead
• The same logic applies vice versa

This greedy approach works because:

1. We're looking for the earliest valid time
2. By processing intervals in sorted order, the first valid overlap we find is guaranteed to be the earliest
3. We never need to backtrack because if intervals i and j don't have sufficient overlap, and interval i ends first, then interval i won't have sufficient overlap with any interval after j either

The algorithm elegantly handles all cases: completely non-overlapping intervals, partial overlaps that are too short, and overlaps that satisfy our duration requirement.

Learn more about Two Pointers and Sorting patterns.

Solution Approach

The implementation follows a sorting + two pointers pattern to efficiently find the earliest common available time slot.

Step 1: Sort Both Arrays

slots1.sort()
slots2.sort()

We sort both arrays by their start times (Python's default sorting for lists of lists sorts by the first element). This ensures we examine potential meeting times in chronological order.

Step 2: Initialize Two Pointers

m, n = len(slots1), len(slots2)
i = j = 0

We use pointer i for slots1 and pointer j for slots2, starting both at index 0.

Step 3: Find Overlapping Intervals

while i < m and j < n:
    start = max(slots1[i][0], slots2[j][0])
    end = min(slots1[i][1], slots2[j][1])

For each pair of intervals, we calculate:

• The overlap starts at the later of the two start times: max(slots1[i][0], slots2[j][0])
• The overlap ends at the earlier of the two end times: min(slots1[i][1], slots2[j][1])

Step 4: Check if Overlap is Sufficient

if end - start >= duration:
    return [start, start + duration]

If the overlap duration (end - start) is at least duration minutes, we've found our answer. We return the interval [start, start + duration] as the earliest valid meeting time.

Step 5: Advance the Appropriate Pointer

if slots1[i][1] < slots2[j][1]:
    i += 1
else:
    j += 1

If no valid meeting is found with the current pair:

• If person 1's interval ends earlier, move to their next interval (i += 1)
• Otherwise, move to person 2's next interval (j += 1)

This ensures we don't miss any potential overlaps while avoiding unnecessary comparisons.

Step 6: Return Empty Array if No Solution

return []

If we exhaust either array without finding a valid meeting time, return an empty array.

Time Complexity: O(m log m + n log n) for sorting, where m and n are the lengths of the two arrays. The two-pointer traversal is O(m + n).

Space Complexity: O(1) if we don't count the space used for sorting (or O(log m + log n) for the sorting stack space).

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach:

Input:

• slots1 = [[10, 50], [60, 120], [140, 210]]
• slots2 = [[0, 15], [60, 70]]
• duration = 8

Step 1: Sort both arrays (already sorted in this case)

• slots1 = [[10, 50], [60, 120], [140, 210]]
• slots2 = [[0, 15], [60, 70]]

Step 2: Initialize pointers

• i = 0 (pointing to [10, 50] in slots1)
• j = 0 (pointing to [0, 15] in slots2)

Step 3: First iteration

• Current intervals: [10, 50] and [0, 15]
• Calculate overlap:
  • start = max(10, 0) = 10
  • end = min(50, 15) = 15
• Overlap duration: 15 - 10 = 5 (less than 8, not sufficient)
• Since slots1[0][1] = 50 > slots2[0][1] = 15, advance j to 1

Step 4: Second iteration

• Current intervals: [10, 50] and [60, 70]
• Calculate overlap:
  • start = max(10, 60) = 60
  • end = min(50, 70) = 50
• Since 60 > 50, there's no overlap (invalid interval)
• Since slots1[0][1] = 50 < slots2[1][1] = 70, advance i to 1

Step 5: Third iteration

• Current intervals: [60, 120] and [60, 70]
• Calculate overlap:
  • start = max(60, 60) = 60
  • end = min(120, 70) = 70
• Overlap duration: 70 - 60 = 10 (greater than 8, sufficient!)
• Return [60, 60 + 8] = [60, 68]

Result: [60, 68] - Both people are available from time 60 to 70, so they can meet from 60 to 68 (8 minutes).

This example demonstrates how the algorithm:

1. Examines intervals in chronological order
2. Calculates overlaps between pairs of intervals
3. Advances the pointer whose interval ends earlier
4. Returns immediately upon finding the first valid meeting time

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × log m + n × log n)

The time complexity is dominated by the sorting operations:

• Sorting slots1 takes O(m × log m) time where m is the length of slots1
• Sorting slots2 takes O(n × log n) time where n is the length of slots2
• The while loop performs a two-pointer traversal through both sorted arrays, which takes O(m + n) time in the worst case

Therefore, the overall time complexity is O(m × log m + n × log n + m + n), which simplifies to O(m × log m + n × log n) since the sorting operations dominate.

Space Complexity: O(log m + log n)

The space complexity comes from the sorting operations:

• Python's built-in sort() method uses Timsort algorithm, which requires O(log m) space for sorting slots1 in the worst case
• Similarly, sorting slots2 requires O(log n) space
• The remaining variables (i, j, start, end) use constant O(1) space

Therefore, the total space complexity is O(log m + log n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Sort the Input Arrays

One of the most common mistakes is assuming the input arrays are already sorted and skipping the sorting step. The problem statement doesn't guarantee that slots are given in chronological order.

Incorrect Code:

def minAvailableDuration(self, slots1, slots2, duration):
    # WRONG: Directly using arrays without sorting
    i = j = 0
    while i < len(slots1) and j < len(slots2):
        start = max(slots1[i][0], slots2[j][0])
        end = min(slots1[i][1], slots2[j][1])
        # ... rest of logic

Why it fails: Without sorting, you might miss the earliest valid slot. For example:

• slots1 = [[50, 60], [10, 20]]
• slots2 = [[15, 25], [55, 65]]
• duration = 5
• Without sorting, you'd check [50,60] with [15,25] first and miss the earlier valid overlap at [15,20]

Solution: Always sort both arrays at the beginning:

slots1.sort()
slots2.sort()

2. Incorrect Overlap Calculation

Another pitfall is incorrectly calculating whether two intervals overlap or the duration of their overlap.

Incorrect Code:

# WRONG: Using subtraction in wrong order
if slots1[i][1] - slots2[j][0] >= duration:
    return [slots2[j][0], slots2[j][0] + duration]

Why it fails: This doesn't correctly check if both people are available. The overlap must consider both intervals' constraints.

Solution: Calculate overlap correctly:

start = max(slots1[i][0], slots2[j][0])  # Later start time
end = min(slots1[i][1], slots2[j][1])    # Earlier end time
if end - start >= duration:              # Check if overlap is sufficient
    return [start, start + duration]

3. Wrong Pointer Advancement Logic

A subtle mistake is advancing the wrong pointer or advancing both pointers simultaneously.

Incorrect Code:

# WRONG: Always advancing both pointers
if end - start >= duration:
    return [start, start + duration]
i += 1
j += 1

Why it fails: This skips potential valid overlaps. If slot1[0] = [10,20] and slot2[0] = [15,30], after checking them, we should only advance pointer for slots1 (since it ends first), not both.

Solution: Advance only the pointer whose interval ends earlier:

if slots1[i][1] < slots2[j][1]:
    i += 1
else:
    j += 1

4. Edge Case: Zero or Negative Overlap

Not handling cases where intervals don't overlap at all (when end < start).

Incorrect Code:

start = max(slots1[i][0], slots2[j][0])
end = min(slots1[i][1], slots2[j][1])
# WRONG: Not checking if there's actual overlap
if end - start >= duration:  # This could be negative!
    return [start, start + duration]

Why it fails: When intervals don't overlap, end < start, making end - start negative. While the condition would still fail (negative < positive duration), it's better to be explicit.

Solution: You can add an explicit check or rely on the mathematical property:

start = max(slots1[i][0], slots2[j][0])
end = min(slots1[i][1], slots2[j][1])
# The condition naturally handles non-overlapping cases
if end - start >= duration:  # When end < start, this is always false
    return [start, start + duration]

5. Returning Wrong Meeting End Time

Returning [start, end] instead of [start, start + duration].

Incorrect Code:

if end - start >= duration:
    # WRONG: Using the overlap end instead of start + duration
    return [start, end]

Why it fails: The meeting should be exactly duration minutes long, not the entire overlap period.

Solution: Return the meeting slot with exact duration:

return [start, start + duration]