Problem Description

The Meeting Scheduler problem asks you to find the earliest time slot that works for both people to have a meeting of a given duration, given each person's available time slots.

You are given two lists, slots1 and slots2, where each element is a list of two integers [start, end] representing an available time slot in minutes. You are also given an integer duration representing the length of the meeting in minutes.

• Each slot is closed at the start and open at the end: [start, end)
• Slots are not guaranteed to be sorted or non-overlapping.
• You must return the earliest possible time slot [start, start + duration] that is available in both slots1 and slots2.
• If there is no suitable slot, return an empty list [].
• Only one valid answer is required; do not reuse or split slots.

Thought Process

At first glance, it seems like you could compare every possible pair of slots from slots1 and slots2 to check if they overlap for at least duration minutes. However, this brute-force approach would be slow if there are many slots.

To optimize, notice that we only care about overlapping intervals that are at least as long as duration. If we sort both lists by start time, we can efficiently walk through both lists (like merging two sorted lists), always advancing the slot that ends earlier. This way, we never revisit unnecessary comparisons, and we always check for the earliest possible overlap.

The key insight is to treat the problem like a two-pointer merge, focusing only on overlaps and moving forward as soon as a slot can't possibly help.

Solution Approach

• Step 1: Filter out slots that are shorter than duration in both slots1 and slots2, since they can't possibly fit the meeting.
• Step 2: Sort both slots1 and slots2 by their start times. This allows us to efficiently scan for overlaps.
• Step 3: Use two pointers, i for slots1 and j for slots2. At each step, compare slots1[i] and slots2[j]:
  • Calculate the overlap: max(start1, start2) to min(end1, end2).
  • If the overlap is at least duration, return [overlap_start, overlap_start + duration].
  • Otherwise, advance the pointer that points to the interval that ends earlier (since it can't help anymore).
• Step 4: If you reach the end of either list without finding a slot, return an empty list.

This approach is efficient because each slot is only considered once, and we avoid unnecessary comparisons.

Example Walkthrough

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

• Sort and filter: All slots are at least 8 minutes.
• Compare [10, 50] (from slots1) and [0, 15] (from slots2):
  • Overlap is from 10 to 15 (5 minutes), which is less than 8.
  • Advance slots2 pointer, since [0, 15] ends earlier.
• Compare [10, 50] and [60, 70]:
  • Overlap is from 60 to 50, which is negative (no overlap).
  • Advance slots1 pointer, since [10, 50] ends earlier.
• Compare [60, 120] and [60, 70]:
  • Overlap is from 60 to 70 (10 minutes), which is at least 8.
  • Return [60, 68] as the earliest slot.

Code Implementation

class Solution:
    def minAvailableDuration(self, slots1, slots2, duration):
        # Filter out slots shorter than duration
        slots1 = [s for s in slots1 if s[1] - s[0] >= duration]
        slots2 = [s for s in slots2 if s[1] - s[0] >= duration]
        # Sort both lists by start time
        slots1.sort()
        slots2.sort()
        i, j = 0, 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])
            if end - start >= duration:
                return [start, start + duration]
            if slots1[i][1] < slots2[j][1]:
                i += 1
            else:
                j += 1
        return []
      

class Solution {
public:
    vector<int> minAvailableDuration(vector<vector<int>>& slots1, vector<vector<int>>& slots2, int duration) {
        vector<vector<int>> s1, s2;
        for (auto& s : slots1)
            if (s[1] - s[0] >= duration) s1.push_back(s);
        for (auto& s : slots2)
            if (s[1] - s[0] >= duration) s2.push_back(s);
        sort(s1.begin(), s1.end());
        sort(s2.begin(), s2.end());
        int i = 0, j = 0;
        while (i < s1.size() && j < s2.size()) {
            int start = max(s1[i][0], s2[j][0]);
            int end = min(s1[i][1], s2[j][1]);
            if (end - start >= duration)
                return {start, start + duration};
            if (s1[i][1] < s2[j][1]) ++i;
            else ++j;
        }
        return {};
    }
};
      

class Solution {
    public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {
        List<int[]> s1 = new ArrayList<>();
        List<int[]> s2 = new ArrayList<>();
        for (int[] s : slots1)
            if (s[1] - s[0] >= duration) s1.add(s);
        for (int[] s : slots2)
            if (s[1] - s[0] >= duration) s2.add(s);
        s1.sort((a, b) -> a[0] - b[0]);
        s2.sort((a, b) -> a[0] - b[0]);
        int i = 0, j = 0;
        while (i < s1.size() && j < s2.size()) {
            int start = Math.max(s1.get(i)[0], s2.get(j)[0]);
            int end = Math.min(s1.get(i)[1], s2.get(j)[1]);
            if (end - start >= duration)
                return Arrays.asList(start, start + duration);
            if (s1.get(i)[1] < s2.get(j)[1]) i++;
            else j++;
        }
        return new ArrayList<>();
    }
}
      

var minAvailableDuration = function(slots1, slots2, duration) {
    slots1 = slots1.filter(s => s[1] - s[0] >= duration);
    slots2 = slots2.filter(s => s[1] - s[0] >= duration);
    slots1.sort((a, b) => a[0] - b[0]);
    slots2.sort((a, b) => a[0] - b[0]);
    let i = 0, j = 0;
    while (i < slots1.length && j < slots2.length) {
        let start = Math.max(slots1[i][0], slots2[j][0]);
        let end = Math.min(slots1[i][1], slots2[j][1]);
        if (end - start >= duration)
            return [start, start + duration];
        if (slots1[i][1] < slots2[j][1]) i++;
        else j++;
    }
    return [];
};
      

Time and Space Complexity

• Brute-Force Approach:
  • For every slot in slots1, compare to every slot in slots2: O(N * M) time, where N and M are the lengths of the input lists.
  • Space: O(1) extra (not counting input).
• Optimized Approach (Two-Pointer):
  • Sorting both lists: O(N log N + M log M)
  • Two-pointer scan: O(N + M)
  • Total time: O(N log N + M log M)
  • Space: O(N + M) for filtered lists (or O(1) if done in-place).
• The optimized approach is much faster when the lists are large.

Summary

The Meeting Scheduler problem is a classic interval overlap challenge. By filtering, sorting, and using a two-pointer technique, we efficiently find the earliest overlapping slot of sufficient duration. This approach avoids unnecessary comparisons and leverages sorting for optimal performance. The key insight is to always advance the pointer with the earlier end time, ensuring we never miss a potential overlap. This makes the solution both elegant and efficient.