Formatted question description: https://leetcode.ca/all/1229.html

1229. Meeting Scheduler

Level

Medium

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 <= 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

First, sort both slots1 and slots2 according to start time in ascending order.

Next, use two indices for both slots arrays to point to slots. If the two slots from two arrays have no intersection, then find the index of the slot with a smaller end time, and increase the index by 1. If the two slots from two arrays have intersection, then check whether the intersection range is at least duration. If so, obtain the smallest possible start and set end = start + duration, add both start and end to the result list, and return the result list. Otherwise, find the index of the slot with a smaller end time, and increase the index by 1. If both slots have the same end time, then increase both indices by 1. If no common time slot with range duration is found, return an empty list.

public class Meeting_Scheduler {

    public static void main(String[] args) {
        Meeting_Scheduler out = new Meeting_Scheduler();
        Solution_pq s = out.new Solution_pq();

        System.out.println(s.minAvailableDuration(new int[][]{ {10,50}, {60,120}, {140,210} }, new int[][]{ {0,15}, {60,70} }, 8));
        System.out.println(s.minAvailableDuration(new int[][]{ {10,50}, {60,120}, {140,210} }, new int[][]{ {0,15}, {60,70} }, 12));


        Solution sss= out.new Solution();
        System.out.println(sss.minAvailableDuration(new int[][]{ {10,50}, {60,120}, {140,210} }, new int[][]{ {0,15}, {60,70} }, 8));
        System.out.println(sss.minAvailableDuration(new int[][]{ {10,50}, {60,120}, {140,210} }, new int[][]{ {0,15}, {60,70} }, 12));
    }

    class Solution_pq {
        public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {

            // null check

            // order by start time
            PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparing(a -> a[0]));
            for (int[] s : slots1) {
                if (s[1] - s[0] >= duration) {
                    pq.offer(s);
                }
            }
            for (int[] s : slots2) {
                if (s[1] - s[0] >= duration) {
                    pq.offer(s);
                }
            }

            while (pq.size() > 1) {
                // @note: poll出来的start已经是<= peek的start，只要poll出来的end够peek的end加duration
                // assumption: 同一个人的slot不会有重叠
                if (pq.poll()[1] >= pq.peek()[0] + duration) {
                    return Arrays.asList(pq.peek()[0], pq.peek()[0] + duration);
                }
            }
            return Arrays.asList();
        }
    }


    // 首先对slots1和slots2分别按start排好序。接下来分别从slots1和slots2中取第一个元素，判断两个元素是否满足会议，
    // 如果不满足，则从end较小的元素对应的slots中取后一个元素。以此类推，直到找出符合条件的slot为止。
    class Solution {
        public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {

            // 按照开始时间排序
            Comparator c = (Comparator<int[]>) (o1, o2) -> o1[0] - o2[0];

            Arrays.sort(slots1, c); // 排序slots1
            Arrays.sort(slots2, c); // 排序slots2

            int i1 = 0, i2 = 0; // 起始时，客户1和客户2的下标均为0
            while (i1 < slots1.length && i2 < slots2.length) {
                // 客户1的结束时间小于客户2的开始时间，两者不相交
                if (slots1[i1][1] < slots2[i2][0]) {
                    i1++; // 客户1的index加一
                }
                // 客户2的结束时间小于客户1的开始时间，两者不相交
                else if (slots2[i2][1] < slots1[i1][0]) {
                    i2++; // 客户2的index加一
                }

                else {
                    int startTentative = Math.max(slots1[i1][0], slots2[i2][0]);
                    int endTentative = Math.min(slots1[i1][1], slots2[i2][1]);

                    if (endTentative - startTentative >= duration) {
                        return Arrays.asList(startTentative, startTentative + duration);
                    }
                }

                /*
                // 客户2是客户1的子集
                else if (slots1[i1][0] <= slots2[i2][0]
                    && slots1[i1][1] >= slots2[i2][1]) {
                    // 当客户2的时间区间长度大于等于duration
                    if (slots2[i2][1] - slots2[i2][0] >= duration) {
                        // 返回合理区间
                        return getList(slots2[i2][0], duration);
                    }
                    i2++; // 客户2的index加一
                }
                // 客户1是客户2的子集
                else if (slots2[i2][0] <= slots1[i1][0]
                    && slots2[i2][1] >= slots1[i1][1]) {
                    // 当客户1的时间区间长度大于等于duration
                    if (slots1[i1][1] - slots1[i1][0] >= duration) {
                        // 返回合理区间
                        return getList(slots1[i1][0], duration);
                    }
                    i1++; // 客户1的index加一
                }
                // 客户1和客户2有部分交集（客户2在前）
                else if (slots2[i2][1] >= slots1[i1][0]
                    && slots2[i2][0] < slots1[i1][0]) {
                    if (slots2[i2][1] - slots1[i1][0] >= duration) {
                        return getList(slots1[i1][0], duration);
                    }
                    i2++;
                }
                // 客户1和客户2有部分交集（客户1在前）
                else if (slots1[i1][1] >= slots2[i2][0]
                    && slots1[i1][0] < slots2[i2][0]) {
                    if (slots1[i1][1] - slots2[i2][0] >= duration) {
                        return getList(slots2[i2][0], duration);
                    }
                    i1++;
                }
                */
            }
            return new ArrayList<>();
        }

        /*
        List<Integer> getList(int start, int duration) {
            List<Integer> res = new ArrayList<>();
            res.add(start);
            res.add(start + duration);
            return res;
        }
        */
    }
}

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 []

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

'''
>>> 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]
'''
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 []


# Time:  O(nlogn)
# Space: O(n)
class Solution2(object):
    def minAvailableDuration(self, slots1, slots2, duration):
        """
        :type slots1: List[List[int]]
        :type slots2: List[List[int]]
        :type duration: int
        :rtype: List[int]
        """
        slots1.sort(key = lambda x: x[0])
        slots2.sort(key = lambda x: x[0])
        i, j = 0, 0
        while i < len(slots1) and j < len(slots2):
            left = max(slots1[i][0], slots2[j][0])
            right = min(slots1[i][1], slots2[j][1])
            if left+duration <= right:
                return [left, left+duration]
            if slots1[i][1] < slots2[j][1]:
                i += 1
            else:
                j += 1
        return []

1229 - Meeting Scheduler

1229. Meeting Scheduler

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

1229. Meeting Scheduler

Level

Description

Solution

All Problems

All Solutions