LeetCode 757: Set Intersection Size At Least Two

Problem Description

LeetCode Problem 757

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

Difficulty: Hard

Tags: array, greedy, sorting

Rating: 89.57%

Approach

The key insight to solving this problem efficiently is to use a greedy approach:

1. First, sort the intervals by end point. This ensures we process intervals in order of their ending points.
2. For each interval, we need to check how many points from our existing set fall within it.
3. If we need more points, we add them as late as possible in the interval.

Why Sort by End Point?

Sorting by end point is crucial because:

• It allows us to process intervals in a way that minimizes conflicts
• Later intervals can potentially reuse points from earlier intervals
• We can make greedy choices about where to place new points

Python Implementation

class Solution:
    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:
        # Sort intervals by end point
        intervals.sort(key=lambda x: x[1])
        points = []
        
        for start, end in intervals:
            # Count points that lie within current interval
            count = sum(1 for p in points if start <= p <= end)
            
            # Add needed points based on how many we already have
            if count == 0:
                # Need two points, add end-1 and end
                points.append(end-1)
                points.append(end)
            elif count == 1:
                # Need one more point
                if points[-1] == end:
                    points.append(end-1)
                else:
                    points.append(end)
        
        return len(points)

Step-by-Step Walkthrough:

1. Initial state: intervals = [[1,3], [3,7], [8,9]] After sorting: Same (already sorted by end point)

2. Processing [1,3]:

   • Current points: []
   • Need 2 points → Add [2,3]
   • Points after: [2,3]

3. Processing [3,7]:

   • Current points: [2,3]
   • Only 1 point (3) is in interval
   • Need 1 more point → Add 7
   • Points after: [2,3,7]

4. Processing [8,9]:

   • Current points: [2,3,7]
   • No points in interval
   • Need 2 points → Add [8,9]
   • Final points: [2,3,7,8,9]

Final result: 5 points needed

Complexity Analysis

• Time Complexity: $O(n log n)$ due to sorting
• Space Complexity: $O(n)$ to store the result points

Key Insights

1. The greedy strategy of placing points at the end of intervals works because:

   • It maximizes the chance of reusing points for later intervals
   • It ensures we maintain the minimum necessary points

2. When adding points, we need to be careful about their placement:

   • If we need two points, we add them at end-1 and end
   • If we need one point, we need to check if the existing point is at the end