1229. Meeting Scheduler - Solution & Explanation

The problem

Given the availability time slots arrays slots1 and slots2 of two people and a meeting duration duration, return the earliest time slot that works for both of them and is of duration 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.

It is guaranteed that no two availability slots of the same person intersect with each other. That is, for any two time slots [start1, end1] and [start2, end2] of the same person, either start1 > end2 or start2 > end1.

Example 1:

Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8
Output: [60,68]

Example 2:

Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 12
Output: []

Constraints:

1 <= slots1.length, slots2.length <= 10⁴
slots1[i].length, slots2[i].length == 2
slots1[i][0] < slots1[i][1]
slots2[i][0] < slots2[i][1]
0 <= slots1[i][j], slots2[i][j] <= 10⁹
1 <= duration <= 10⁶

Approach overview

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.

Solution

We can sort the free time intervals of both people, then use two pointers to traverse the two arrays and find the intersection of the free time intervals of both people. If the length of the intersection is greater than or equal to duration, return the start time of the intersection and the start time plus duration. Otherwise, if the end time of the first person's free time interval is less than the end time of the second person's free time interval, move the first person's pointer; otherwise, move the second person's pointer. Continue traversing until a suitable time interval is found or the traversal ends.

The time complexity is O(m times log m + n times log n), and the space complexity is O(log m + log n). Here, m and n are the lengths of the two arrays, respectively.

Python

class Solution:
    def minAvailableDuration(
        self, slots1: List[List[int]], slots2: List[List[int]], duration: int
    ) -> List[int]:
        slots1.sort()
        slots2.sort()
        m, n = len(slots1), len(slots2)
        i = j = 0
        while i < m and j < n:
            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 []

Java

class Solution {
    public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {
        Arrays.sort(slots1, (a, b) -> a[0] - b[0]);
        Arrays.sort(slots2, (a, b) -> a[0] - b[0]);
        int m = slots1.length, n = slots2.length;
        int i = 0, j = 0;
        while (i < m && j < n) {
            int start = Math.max(slots1[i][0], slots2[j][0]);
            int end = Math.min(slots1[i][1], slots2[j][1]);
            if (end - start >= duration) {
                return Arrays.asList(start, start + duration);
            }
            if (slots1[i][1] < slots2[j][1]) {
                ++i;
            } else {
                ++j;
            }
        }
        return Collections.emptyList();
    }
}

C++

class Solution {
public:
    vector<int> minAvailableDuration(vector<vector<int>>& slots1, vector<vector<int>>& slots2, int duration) {
        sort(slots1.begin(), slots1.end());
        sort(slots2.begin(), slots2.end());
        int m = slots1.size(), n = slots2.size();
        int i = 0, j = 0;
        while (i < m && j < n) {
            int start = max(slots1[i][0], slots2[j][0]);
            int end = 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 {};
    }
};

TypeScript

function minAvailableDuration(slots1: number[][], slots2: number[][], duration: number): number[] {
    slots1.sort((a, b) => a[0] - b[0]);
    slots2.sort((a, b) => a[0] - b[0]);
    const [m, n] = [slots1.length, slots2.length];
    let [i, j] = [0, 0];
    while (i < m && j < n) {
        const [start1, end1] = slots1[i];
        const [start2, end2] = slots2[j];
        const start = Math.max(start1, start2);
        const end = Math.min(end1, end2);
        if (end - start >= duration) {
            return [start, start + duration];
        }
        if (end1 < end2) {
            i++;
        } else {
            j++;
        }
    }
    return [];
}

func minAvailableDuration(slots1 [][]int, slots2 [][]int, duration int) []int {
	sort.Slice(slots1, func(i, j int) bool { return slots1[i][0] < slots1[j][0] })
	sort.Slice(slots2, func(i, j int) bool { return slots2[i][0] < slots2[j][0] })
	i, j, m, n := 0, 0, len(slots1), len(slots2)
	for i < m && j < n {
		start := max(slots1[i][0], slots2[j][0])
		end := min(slots1[i][1], slots2[j][1])
		if end-start >= duration {
			return []int{start, start + duration}
		}
		if slots1[i][1] < slots2[j][1] {
			i++
		} else {
			j++
		}
	}
	return []int{}
}

Rust

impl Solution {
    pub fn min_available_duration(mut slots1: Vec<Vec<i32>>, mut slots2: Vec<Vec<i32>>, duration: i32) -> Vec<i32> {
        slots1.sort_by_key(|slot| slot[0]);
        slots2.sort_by_key(|slot| slot[0]);

        let (mut i, mut j) = (0, 0);
        let (m, n) = (slots1.len(), slots2.len());

        while i < m && j < n {
            let (start1, end1) = (slots1[i][0], slots1[i][1]);
            let (start2, end2) = (slots2[j][0], slots2[j][1]);

            let start = start1.max(start2);
            let end = end1.min(end2);

            if end - start >= duration {
                return vec![start, start + duration];
            }

            if end1 < end2 {
                i += 1;
            } else {
                j += 1;
            }
        }

        vec![]
    }
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Interval Comparison	O(n * m)	O(1)	Small inputs or quick prototype to verify overlap logic
Sorting + Two Pointers	O(n log n + m log m)	O(1)	Optimal solution when schedules are arrays of intervals
Min Heap Merge	O((n + m) log(n + m))	O(n + m)	Useful when combining schedules from multiple participants or streams

Frequently asked questions

Is Meeting Scheduler easy or hard?

Meeting Scheduler is generally classified as a medium difficulty problem. The main challenge is recognizing that sorting the intervals allows a linear scan with two pointers, avoiding the O(n * m) brute force comparison of all pairs.

How to solve Meeting Scheduler in O(n)?

A pure O(n) solution is possible only if both slot lists are already sorted by start time. In that case, use two pointers to compare intervals and compute overlaps while advancing the pointer with the earlier ending time. The scan processes each interval once, giving O(n + m) time.

Meeting Scheduler Python or Java solution

Most implementations sort both slot arrays and use two indices to scan for overlapping windows. Python solutions typically use built-in sorting with a simple loop, while Java solutions use Arrays.sort and pointer variables. Both follow the same O(n log n + m log m) algorithm.

What is the best approach for Meeting Scheduler?

The optimal solution uses sorting and the two pointers technique. First sort both slot lists by start time, then scan them simultaneously to compute overlaps. At each step check if the overlap length is at least the required duration. This runs in O(n log n + m log m) time due to sorting and O(1) extra space.

What data structure is used in Meeting Scheduler?

The primary structures are arrays of intervals combined with sorting and the two pointers technique. Some alternative implementations use a min heap to process intervals by start time, but the two pointer scan after sorting is the most common approach.

What is the time complexity of Meeting Scheduler?

The optimal approach runs in O(n log n + m log m) time because both availability lists must be sorted by start time. After sorting, the two pointer scan processes each interval once, which is O(n + m). Space complexity is O(1) if sorting is done in place.

Is Meeting Scheduler asked at Google, Amazon, or Meta?

Meeting Scheduler is a common interval scheduling problem frequently reported in interviews at companies like Google, Amazon, and Meta. It tests understanding of interval overlap, sorting, and the two pointers pattern, which are standard interview topics.

Meeting Scheduler solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Meeting Scheduler solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems