We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Set Intersection Size At Least Two

Number: 759

Difficulty: Hard

Paid? No

Companies: Drawbridge

Problem Description

Given a list of intervals, where each interval represents a set of consecutive integers, find the minimum size of an array such that every interval contains at least two numbers from that array.

Key Insights

  • Use a greedy strategy by processing intervals in order of increasing end points.
  • Sort the intervals by end point (and in case of tie, by start in descending order) so that choosing numbers near the end maximizes coverage for future intervals.
  • For each interval, count the numbers already chosen that fall into the interval.
  • If fewer than two numbers are present, add the necessary number(s) (always choosing the largest possible values within the interval to maximize overlap with future intervals).

Space and Time Complexity

Time Complexity: O(n log n) due to the sorting step where n is the number of intervals. Space Complexity: O(n) for storing the chosen numbers (in worst-case scenarios) plus auxiliary space for sorting.

Solution

The solution uses a greedy approach after sorting the intervals. First, the intervals are sorted by their end boundary, with a tie-breaker on the start boundary (in descending order) to ensure that when intervals share an end, the one with the larger start is handled last. For each interval, we check how many selected numbers (already added in our result set) fall inside the interval. If fewer than two, we add additional numbers at the end of the interval. This ensures that the numbers we add are as large as possible within the current interval, thereby maximizing the chance they will cover future intervals as well. The key idea is that by always “covering” an interval from the end, we are potentially covering as many subsequent intervals as possible.

Code Solutions

Below are the code solutions in Python, JavaScript, C++, and Java.

# Python code solution
from typing import List

class Solution:
    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:
        # sort intervals by end ascending, start descending when ends are equal
        intervals.sort(key=lambda x: (x[1], -x[0]))
        
        result = 0  # count of numbers in the chosen set
        # last two selected numbers; initialize them to values that would not interfere with any interval.
        # They represent the two largest numbers added so far that are used to cover intervals.
        # We initialize them to values that are "unused".
        p, q = -1, -1
        
        for start, end in intervals:
            # Three cases depending on how many of {p, q} fall into the current interval [start, end]
            # Case 1: Both numbers are already in the interval, no addition required
            if start <= p:
                continue
            # Case 2: Only one of the previous numbers is in the interval
            if start <= q:
                # We need to add one number to cover interval, choose end as it is the largest possible in this interval.
                result += 1
                p = q
                q = end
            else:
                # Case 3: None of the previous selected numbers are in the interval.
                # We add two numbers: end-1 and end.
                result += 2
                p = end - 1
                q = end
                
        return result

# Example usage:
# sol = Solution()
# print(sol.intersectionSizeTwo([[1,3],[3,7],[8,9]]))  # Expected output: 5
← Back to All Questions