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.

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

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public List<Integer> minAvailableDuration(int[][] slots1, 
                                              int[][] slots2, 
                                              int duration) {
        Comparator<int[]> comparator = (a, b) -> a[0]-b[0];
        
        Arrays.sort(slots1, comparator);
        Arrays.sort(slots2, comparator);
        
        int ptr1 = 0, ptr2 = 0;
        
        while(ptr1 < slots1.length && ptr2 < slots2.length) {
            int[] slot1 = slots1[ptr1];
            int[] slot2 = slots2[ptr2];
            
            int start = Math.max(slot1[0], slot2[0]);
            int end = Math.min(slot1[1], slot2[1]);
            
            if((start + duration) <= end) {
                return List.of(start, start+duration);
            }
            
            if(slot1[1] > slot2[1]) {
                ptr2++;
            } else {
                ptr1++;
            }
        }
        
        return List.of();
    }
}

Solution 2

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public List<Integer> minAvailableDuration(int[][] slots1, 
                                              int[][] slots2, 
                                              int duration) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);

        for (int[] slot : slots1) {
            if (slot[1] - slot[0] >= duration) {
                pq.offer(slot);
            }
        }

        for (int[] slot : slots2) {
            if (slot[1] - slot[0] >= duration) {
                pq.offer(slot);
            }
        }

        List<Integer> results = new ArrayList<>();
        while (pq.size() > 1) {
            if (pq.poll()[1] - pq.peek()[0] >= duration) {
                results.add(pq.peek()[0]);
                results.add(pq.peek()[0] + duration);

                return results;
            }
        }

        return results;        
    }
}

Follow up