Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Handle intervals with the earliest ending point first. When an interval needs new selected integers, choosing them as far right as possible gives later intervals the best chance to reuse them. Since processed endpoints never decrease, only the two largest selected integers are needed to determine whether the next interval already has two hits.

Approach

Sort by increasing end, breaking ties by decreasing start so narrower same-end intervals come first.
Select the first interval's last two integers and remember them as left and right.
If the next start is at most left, both remembered integers lie inside it and no addition is needed. If it lies between left and right, keep right and add the current end. If it exceeds right, add end - 1 and end.
Update the remembered pair and total count after each addition. Choosing the rightmost feasible replacements never reduces coverage of a later-ending interval, which establishes the greedy minimum.

class Solution:
    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:
        n = len(intervals)
        intervals.sort(reverse = True)
        intervals.sort(key = lambda x: x[1])
        left = intervals[0][1] - 1
        right = intervals[0][1]
        res = 2

        for i in range(1, n):
            start, end = intervals[i]
            if left < start and start <= right:
                res += 1
                left = right
                right = end
            elif start > right:
                res += 2
                left = end - 1
                right = end

        return res

Complexity analysis

For n intervals, sorting dominates at O(n log n) time and the greedy scan is O(n). Auxiliary space is O(1) for the scan, while the language sort may use O(n) workspace.