Problem Statement in English

You’re given a 2D integer array intervals where intervals[i] = [starti, endi] represents an interval from starti to endi (inclusive). Your task is to return the minimum size of a set S such that for every interval [i, j] in intervals, the intersection of S with the interval has at least two elements.

Approach

I watched NeetCode’s video solution and it made this seem so very simple. As usual.

The title already gives us a hint that this is a sweep line/interval problem.

The trick is to sort the intervals by their end points, and in case of ties, by their start points in descending order.

The intuition behind prioritising the end point in ascending order is that we prefer intervals that end earlier, allowing us to cover them with the least number of points.

The reason for sorting the start points in descending order after soring the end points in ascending order is to ensure that when two intervals have the same end point, we process the one that starts later before we process the one that starts earlier. This again helps in minimizing the number of points needed to cover both intervals since we exploit their overlap.

We maintain 2 pointers p1 and p2 which represent the last two points we have added to our set S. To simplify the logic we ensure that p1 is always less than p2. This helps us easily check if the current interval is already covered by our set S. And the logic for reconcilation when p1 < start of the current interval becomes easy with this rule.

When p2 < start of the current interval, it means that both our pointers are not yet within this new interval, which means we greedily move p1 and p2 to the end of the current interval - 1, and end of current interval, thus adding 22 new points to our set S.

When only p1 < start of the current interval, it means that only one of our pointers is within this new interval, so we move p1 to p2 (which is somewhere near the beginning of the current interval) and p2 to the end of the current interval, thus adding 11 new point to our set S.

Initialising p1 and p2 to -1 is merely an implementation detail to ensure that the first interval always triggers the addition of 22 new points.

Solution in Python


class Solution:
    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:
        res = 0
        intervals.sort(key=lambda x: (x[1], -x[0]))

        p1,p2 = -1,-1

        for start, stop in intervals:
            if p2 < start:
                res += 2
                p2 = stop
                p1 = p2 - 1
            elif p1 < start:
                res += 1
                p1 = p2
                p2 = stop

        return res

Complexity

  • Time: O(nlog⁡n)O(n \log n)
    We sort the intervals which takes O(nlog⁡n)O(n \log n) time and then we traverse the list of intervals once.

  • Space: O(1)O(1)
    Since we use only a constant amount of extra space.

Mistakes I Made

I had to watch the solution.

And we are done.