Meeting Scheduler

medium two pointers intervals sorting

Problem

Given the availability time slots arrays slotsA and slotsB of two people and a meeting duration, return the earliest time slot that works for both of them and is of duration. If there is no common time slot that satisfies the requirements, return an empty array. The format of a time slot is an array of two elements [start, end] representing an inclusive time range from start to end.

InputslotsA = [[10,50],[60,120],[140,210]], slotsB = [[0,15],[60,70]], duration = 8

Output[60, 68]

Both are free in [60, 70]; that overlap is 10 long, so the meeting starts at 60 and ends at 60 + 8 = 68.

slotsA (e.g. [10,50],[60,120])

slotsB

duration

def min_available_duration(slots_a, slots_b, duration):
    slots_a.sort()
    slots_b.sort()
    i = j = 0
    while i < len(slots_a) and j < len(slots_b):
        start = max(slots_a[i][0], slots_b[j][0])
        end = min(slots_a[i][1], slots_b[j][1])
        if end - start >= duration:
            return [start, start + duration]
        if slots_a[i][1] < slots_b[j][1]:
            i += 1
        else:
            j += 1
    return []

function minAvailableDuration(slotsA, slotsB, duration) {
  slotsA.sort((p, q) => p[0] - q[0]);
  slotsB.sort((p, q) => p[0] - q[0]);
  let i = 0, j = 0;
  while (i < slotsA.length && j < slotsB.length) {
    const start = Math.max(slotsA[i][0], slotsB[j][0]);
    const end = Math.min(slotsA[i][1], slotsB[j][1]);
    if (end - start >= duration) return [start, start + duration];
    if (slotsA[i][1] < slotsB[j][1]) i++;
    else j++;
  }
  return [];
}

class Solution {
    public List<Integer> minAvailableDuration(int[][] slotsA, int[][] slotsB, int duration) {
        Arrays.sort(slotsA, (p, q) -> p[0] - q[0]);
        Arrays.sort(slotsB, (p, q) -> p[0] - q[0]);
        int i = 0, j = 0;
        while (i < slotsA.length && j < slotsB.length) {
            int start = Math.max(slotsA[i][0], slotsB[j][0]);
            int end = Math.min(slotsA[i][1], slotsB[j][1]);
            if (end - start >= duration) return Arrays.asList(start, start + duration);
            if (slotsA[i][1] < slotsB[j][1]) i++;
            else j++;
        }
        return new ArrayList<>();
    }
}

vector<int> minAvailableDuration(vector<vector<int>>& slotsA, vector<vector<int>>& slotsB, int duration) {
    sort(slotsA.begin(), slotsA.end());
    sort(slotsB.begin(), slotsB.end());
    int i = 0, j = 0;
    while (i < (int)slotsA.size() && j < (int)slotsB.size()) {
        int start = max(slotsA[i][0], slotsB[j][0]);
        int end = min(slotsA[i][1], slotsB[j][1]);
        if (end - start >= duration) return { start, start + duration };
        if (slotsA[i][1] < slotsB[j][1]) i++;
        else j++;
    }
    return {};
}

Explanation

We want the earliest time both people are free for a block of length duration. After sorting both schedules by start time, we sweep through them together with two pointers i (into A) and j (into B), comparing one slot from each at a time.

For the current pair of slots, the shared free time is their overlap: it begins at the later start, start = max(A[i].start, B[j].start), and ends at the earlier end, end = min(A[i].end, B[j].end). If end - start >= duration, the meeting fits and we return [start, start + duration].

If the overlap is too short, we advance the pointer whose slot ends first, since that slot can never help any later slot of the other person. This keeps both pointers moving forward and the earliest answer guaranteed.

Example: slotsA = [[10,50],[60,120],[140,210]], slotsB = [[0,15],[60,70]], duration = 8. The slots [60,120] and [60,70] overlap in [60,70], a 10-long window, which fits 8. So the meeting is [60, 68].

If a pointer runs off the end without a fit, there is no common slot and we return an empty array.

Time: O(n log n + m log m) Space: O(log n + log m)