Problem of The Day: Meeting Scheduler

Problem Statement

Intuition

When I first looked at this problem, I realized that it is about finding a common time slot between two people’s available slots. My first thought is that sorting both time slot lists will help in comparing them more easily. By sorting, I can then focus on checking the overlapping slots to see if the overlap is long enough to fit the required duration.

Approach

The approach is to first sort both lists of available slots. Then, I compare intervals from each list to find overlapping sections. I go through each pair of intervals, checking if their overlap is greater than or equal to the required duration. If I find such an overlap, I return the start and end time of that overlap. To achieve this, I use two pointers, one for each list of slots, and move them based on the end times of the current intervals.

Complexity

• Time complexity: Sorting both slot lists will take \(O(n \log n)\), where \(n\) is the number of slots in the longer list. After sorting, we traverse both lists, which is \(O(n + m)\) where \(n\) and \(m\) are the lengths of the two lists. Overall, the time complexity is \(O(n \log n + m \log m)\).

• Space complexity: The space complexity is \(O(1)\), since we are using constant extra space beyond the input lists.

Code

class Solution:
    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:
        i = j = 0
        slots1.sort()
        slots2.sort()
        len1, len2 = len(slots1), len(slots2)
        while i < len1 and j < len2:
            start1, end1 = slots1[i]
            start2, end2 = slots2[j]
            if start1 <= start2 < end1:
                if min(end1, end2) - start2 >= duration:
                    return [start2, start2 + duration]

            elif start2 <= start1 < end2:
                if min(end2, end1) - start1 >= duration:
                    return [start1, start1 + duration]

            if end1 < end2:
                i += 1
            else:
                j += 1
        return []

Editorial

Approach 1: Two pointers

class Solution:
    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:

        slots1.sort()
        slots2.sort()
        pointer1 = pointer2 = 0

        while pointer1 < len(slots1) and pointer2 < len(slots2):
            # find the boundaries of the intersection, or the common slot
            intersect_right = min(slots1[pointer1][1], slots2[pointer2][1])
            intersect_left = max(slots1[pointer1][0],slots2[pointer2][0])
            if intersect_right - intersect_left >= duration:
                return [intersect_left, intersect_left + duration]
            # always move the one that ends earlier
            if slots1[pointer1][1]< slots2[pointer2][1]:
                pointer1 += 1
            else:
                pointer2 += 1
        return []

• time: O(MlogM + NlogN)
• space: O(1)

Approach 2: Heap

class Solution:
    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:
        # build up a heap containing time slots last longer than duration
        timeslots = list(filter(lambda x: x[1] - x[0] >= duration, slots1 + slots2))
        heapq.heapify(timeslots)

        while len(timeslots) > 1:
            start1, end1 = heapq.heappop(timeslots)
            start2, end2 = timeslots[0]
            if end1 >= start2 + duration:
                return [start2, start2 + duration]
        return []

• time: O((M + N) log (M + N))
• space: O(M + N)