BinarySearch 0655 Minimum Size of Two Non-Overlapping Intervals

Problem statement

https://binarysearch.com/problems/Minimum-Size-of-Two-Non-Overlapping-Intervals/

Solution

Sort intervals by its ends. Then for each interval (x, y) we need to look at all intervals with end < x, for this we use cumulative minimum of suffixes.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, I):
        I = sorted(I)
        acc = list(accumulate([y - x for x, y in I[::-1]], min))[::-1]
        ans = float("inf")
        for x, y in I:
            idx = bisect.bisect(I, [y, float("inf")])  
            if idx < len(I):
                ans = min(ans, y - x + 1 + acc[idx] + 1)

        return ans if ans != float("inf") else 0