BinarySearch 0854 Meeting Schedule For Two People

Problem statement

https://binarysearch.com/problems/Meeting-Schedule-For-Two-People/

Solution

Variation of Leetcode 0986. Interval List Intersections.

Complexity

It is O(n + m) for time and space.

Code

class Solution:
    def solve(self, A, B, duration):
        i, j, ans = 0, 0, []
        while i < len(A) and j < len(B):
            curr = [max(A[i][0], B[j][0]), min(A[i][1], B[j][1])]
            if curr[0] <= curr[1]:
                ans += [curr]
                if curr[1] - curr[0] >= duration:
                    return [curr[0], curr[0] + duration]
            if A[i][1] <= B[j][1]:
                i += 1
            else:
                j += 1

        return []