Welcome to Subscribe On Youtube

1229. Meeting Scheduler

Description

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 <= 104
  • 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] <= 109
  • 1 <= duration <= 106

Solutions

Solution 1: Sorting + Two Pointers

We can sort the free time of the two people separately, then use two pointers to traverse the two arrays, find the intersection of the free time periods of the two people, and if the length of the intersection is greater than or equal to duration, then return the start time of the intersection and the start time plus duration.

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

  • 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();
    }
}

  • 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 {};
    }
};

  • 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]: # note: ending time later, then keep
                i += 1
            else:
                j += 1
        return []

############

from typing import List

class Solution:
    def findAvailable(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:
        merged = sorted(slots1 + slots2, key=lambda slot: slot[0])
        available = list(filter(lambda x, y: y[0] - x[1] >= duration, zip(merged, merged[1:])))

        return [available[0], available[0] + duration] if available else []

############

'''
>>> a = [1,2,3,4,5,6,7,8,9]
>>> a
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> b = filter(lambda x: x >= 5, a)
>>> b
[5, 6, 7, 8, 9]
'''

# Time:  O(nlogn)
# Space: O(n)
import heapq
class Solution(object):
    def minAvailableDuration(self, slots1, slots2, duration):
        """
        :type slots1: List[List[int]]
        :type slots2: List[List[int]]
        :type duration: int
        :rtype: List[int]
        """
        min_heap = list(filter(lambda slot: slot[1] - slot[0] >= duration, slots1 + slots2))
        heapq.heapify(min_heap)  # Time: O(n)
        while len(min_heap) > 1:
            left = heapq.heappop(min_heap)  # Time: O(logn)
            right = min_heap[0]
            if left[1]-right[0] >= duration:
                return [right[0], right[0]+duration]
        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{}
}

  • impl Solution {
    #[allow(dead_code)]
    pub fn min_available_duration(
        slots1: Vec<Vec<i32>>,
        slots2: Vec<Vec<i32>>,
        duration: i32
    ) -> Vec<i32> {
        let mut slots1 = slots1;
        let mut slots2 = slots2;

        // First sort the two vectors based on the beginning time
        slots1.sort_by(|lhs, rhs| { lhs[0].cmp(&rhs[0]) });
        slots2.sort_by(|lhs, rhs| { lhs[0].cmp(&rhs[0]) });

        // Then traverse the two vector
        let mut i: usize = 0;
        let mut j: usize = 0;
        let N = slots1.len();
        let M = slots2.len();

        while i < N && j < M {
            let (start, end) = (slots1[i][0], slots1[i][1]);
            while j < M && slots2[j][0] < end {
                // If still in the scope
                let (cur_x, cur_y) = (
                    std::cmp::max(start, slots2[j][0]),
                    std::cmp::min(end, slots2[j][1]),
                );
                if cur_y - cur_x >= duration {
                    return vec![cur_x, cur_x + duration];
                }
                // Otherwise, keep iterating
                if slots1[i][1] < slots2[j][1] {
                    // Update i then
                    break;
                }
                j += 1;
            }
            i += 1;
        }

        // The default is an empty vector
        vec![]
    }
}

All Problems

All Solutions