1229. Meeting Scheduler

 一刷 07/2022

Version #1 Two Pointers

KEY: Always move the one that ends earlier when there's overlap

Time O(MlogM + NlogN)

Space O(M + N) used by the sorting algorithm

Runtime: 38 ms, faster than 66.54% of Java online submissions for Meeting Scheduler.

Memory Usage: 67.9 MB, less than 39.92% of Java online submissions for Meeting Scheduler.

class Solution {

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

        // [   ]

        //    [   ]

        // Sort by start time

        Arrays.sort(slots1, (a, b) -> Integer.compare(a[0], b[0]));

        Arrays.sort(slots2, (a, b) -> Integer.compare(a[0], b[0]));

        int p1 = 0, p2 = 0;

        while (p1 < slots1.length && p2 < slots2.length) {

            int start1 = slots1[p1][0];

            int end1 = slots1[p1][1];

            int start2 = slots2[p2][0];

            int end2 = slots2[p2][1];

            if (start1 >= end2) {

                p2++;

                continue;

            }

            if (start2 >= end1) {

                p1++;

                continue;

            }

            int start = Math.max(start2, start1);

            int d = Math.min(end2, end1) - start;

            if (d >= duration) {

                return Arrays.asList(new Integer[]{start, start + duration});

            }

            if (end1 < end2) {

                p1++;

            } else {

                p2++;

            }

        }

        return new ArrayList<>();

    }

}