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.

Examples

Example 1:

1
2

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

Example 2:

1
2

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

Constraints:

  • 1 <= slots1.length, slots2.length <= 10^4
  • 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^9
  • 1 <= duration <= 10^6

Solution

Method 1 – Two Pointers After Sorting

Intuition

By sorting both people’s available slots, we can use two pointers to efficiently find the earliest overlapping slot of at least the required duration.

Approach

  1. Sort both slots1 and slots2 by start time.
  2. Use two pointers to iterate through both lists.
  3. For each pair, compute the overlap interval.
  4. If the overlap is at least duration, return the earliest such slot.
  5. If not, move the pointer with the earlier end time forward.
  6. If no slot is found, return an empty array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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 i = 0, j = 0;
        while (i < slots1.size() && j < slots2.size()) {
            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 {};
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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 := 0, 0
    for i < len(slots1) && j < len(slots2) {
        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{}
}
func min(a, b int) int { if a < b { return a } else { return b } }
func max(a, b int) int { if a > b { return a } else { return b } }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {
        Arrays.sort(slots1, Comparator.comparingInt(a -> a[0]));
        Arrays.sort(slots2, Comparator.comparingInt(a -> a[0]));
        int i = 0, j = 0;
        while (i < slots1.length && j < slots2.length) {
            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 new ArrayList<>();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun minAvailableDuration(slots1: Array<IntArray>, slots2: Array<IntArray>, duration: Int): List<Int> {
        slots1.sortBy { it[0] }
        slots2.sortBy { it[0] }
        var i = 0; var j = 0
        while (i < slots1.size && j < slots2.size) {
            val start = maxOf(slots1[i][0], slots2[j][0])
            val end = minOf(slots1[i][1], slots2[j][1])
            if (end - start >= duration) return listOf(start, start + duration)
            if (slots1[i][1] < slots2[j][1]) i++ else j++
        }
        return emptyList()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def min_available_duration(slots1: list[list[int]], slots2: list[list[int]], duration: int) -> list[int]:
    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 []
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn min_available_duration(slots1: Vec<Vec<i32>>, slots2: Vec<Vec<i32>>, duration: i32) -> Vec<i32> {
        let mut s1 = slots1;
        let mut s2 = slots2;
        s1.sort();
        s2.sort();
        let (mut i, mut j) = (0, 0);
        while i < s1.len() && j < s2.len() {
            let start = s1[i][0].max(s2[j][0]);
            let end = s1[i][1].min(s2[j][1]);
            if end - start >= duration {
                return vec![start, start + duration];
            }
            if s1[i][1] < s2[j][1] { i += 1; } else { j += 1; }
        }
        vec![]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    minAvailableDuration(slots1: number[][], slots2: number[][], duration: number): number[] {
        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) {
            const start = Math.max(slots1[i][0], slots2[j][0]);
            const 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 [];
    }
}

Complexity

  • ⏰ Time complexity: O(n log n + m log m), for sorting both slot lists and linear scan.
  • 🧺 Space complexity: O(1), only pointers and variables used.