{x}
blog image

Set Intersection Size At Least Two

You are given a 2D integer array intervals where intervals[i] = [starti, endi] represents all the integers from starti to endi inclusively.

A containing set is an array nums where each interval from intervals has at least two integers in nums.

  • For example, if intervals = [[1,3], [3,7], [8,9]], then [1,2,4,7,8,9] and [2,3,4,8,9] are containing sets.

Return the minimum possible size of a containing set.

 

Example 1:

Input: intervals = [[1,3],[3,7],[8,9]]
Output: 5
Explanation: let nums = [2, 3, 4, 8, 9].
It can be shown that there cannot be any containing array of size 4.

Example 2:

Input: intervals = [[1,3],[1,4],[2,5],[3,5]]
Output: 3
Explanation: let nums = [2, 3, 4].
It can be shown that there cannot be any containing array of size 2.

Example 3:

Input: intervals = [[1,2],[2,3],[2,4],[4,5]]
Output: 5
Explanation: let nums = [1, 2, 3, 4, 5].
It can be shown that there cannot be any containing array of size 4.

 

Constraints:

  • 1 <= intervals.length <= 3000
  • intervals[i].length == 2
  • 0 <= starti < endi <= 108

Solution Explanation

This problem asks for the minimum size of a containing set, which is a set of numbers such that each interval in the input intervals contains at least two numbers from the set. The solution uses a greedy approach.

Core Idea:

The algorithm sorts the intervals based on their end points. If there are multiple intervals with the same end point, it prioritizes the interval with the smaller starting point. This sorting strategy ensures that intervals with smaller end points are processed first. The algorithm then iteratively builds the containing set by selecting numbers strategically.

Algorithm:

  1. Sort: Sort the input intervals in ascending order based on their end points (intervals[i][1]). If two intervals have the same end point, sort them in descending order of their start points (-intervals[i][0]). This ensures intervals with earlier ending times are considered first, and among those, intervals starting later are preferred.

  2. Greedy Selection: Iterate through the sorted intervals. Maintain two variables, s and e, representing the last two numbers added to the containing set. Initially, s and e are -1.

  3. Interval Processing: For each interval [a, b]:

    • If the interval's start a is less than or equal to s (meaning it already contains at least two numbers), skip this interval.
    • If a is greater than e (meaning it doesn't contain any of the last two numbers added), add two numbers b-1 and b to the set, updating s to b-1 and e to b.
    • Otherwise, if a is greater than s but less than or equal to e (meaning it contains only one of the last two numbers added), add only b to the set, updating s to e and e to b.

  4. Return: The final value of ans (the number of elements added to the containing set) is the minimum size of the containing set.

Time Complexity: O(N log N), dominated by the sorting step, where N is the number of intervals.

Space Complexity: O(1), as the algorithm uses only a constant amount of extra space.

Code Explanation (Python):

class Solution:
    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: (x[1], -x[0])) # Sort as described above
        s = e = -1
        ans = 0
        for a, b in intervals:
            if a <= s:
                continue # Already covered
            if a > e:
                ans += 2
                s, e = b - 1, b # Add two numbers
            else:
                ans += 1
                s, e = e, b # Add one number
        return ans

The other languages (Java, C++, Go) follow the same logic, only differing in syntax and data structure usage. The core greedy selection strategy remains consistent across all implementations.