LeetCode 757 - Set Intersection Size At Least Two

The problem asks us to find the minimum size of a set of integers, nums, such that each given interval [starti, endi] contains at least two integers from nums.

leetcodehardarraygreedysorting

LeetCode Problem 757

Difficulty: 🔴 Hard
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

The problem asks us to find the minimum size of a set of integers, nums, such that each given interval [starti, endi] contains at least two integers from nums. Each interval is represented as a closed interval, meaning all integers between starti and endi inclusive belong to that interval. The goal is to construct nums such that this condition is satisfied for all intervals, but with the smallest possible number of elements.

The input is a 2D array intervals, where 1 <= intervals.length <= 3000 and each interval has 0 <= starti < endi <= 10^8. These constraints imply that a naive approach that enumerates all possible sets is infeasible due to the high potential range of integers and the number of intervals. Edge cases include intervals that overlap completely, intervals that barely touch, and intervals that are minimal in length (size 2, which requires both numbers to be in the set).

The output is a single integer representing the minimum number of integers required in nums to satisfy the "at least two integers per interval" condition.

Approaches

A brute-force approach would attempt to try all possible combinations of integers within the union of all intervals, checking which combination satisfies the condition of at least two integers per interval. While this guarantees correctness, the number of possible sets grows combinatorially with the size of the intervals, making it computationally infeasible given the constraints.

The key insight for an optimal solution is to use a greedy approach with sorting. We can sort the intervals primarily by their end points in ascending order and secondarily by their start points in descending order for intervals with the same end. This ensures that we process intervals from left to right in a way that maximizes reuse of previously selected numbers. We always select the last two largest numbers in each interval if the interval is not already satisfied by existing numbers. By carefully tracking the two largest numbers included from previous intervals, we minimize additional selections.

Approach Time Complexity Space Complexity Notes
Brute Force Exponential O(n) Generate all sets of integers in the intervals and check coverage
Optimal (Greedy + Sorting) O(n log n) O(1) Sort intervals and track last two elements added, extend the set greedily

Algorithm Walkthrough

  1. Sort intervals: Sort the intervals by their end in ascending order. If two intervals have the same end, sort by start in descending order. This ensures that intervals that end earlier are handled first, maximizing the chance that previously added numbers satisfy future intervals.
  2. Initialize two trackers: Maintain two variables, first and second, to track the two largest numbers currently in the containing set. Initialize them to -1 and -1 since no numbers are included yet.
  3. Iterate over intervals: For each interval [start, end], check how many of the current two largest numbers fall within this interval.
  4. Decide numbers to add:
  • If both first and second are in the interval, do nothing.
  • If only second is in the interval, add end to the set and update first and second.
  • If neither are in the interval, add end-1 and end to the set and update first and second.
  1. Return set size: Keep a running count of the total numbers added to nums. At the end, this count is the minimum possible size of the containing set.

Why it works: By always selecting the largest numbers within the interval (greedily), we maximize coverage for future intervals because intervals are sorted by end. This guarantees that the algorithm adds the minimum necessary numbers while maintaining the invariant that every processed interval has at least two numbers.

Python Solution

from typing import List

class Solution:
    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: (x[1], -x[0]))
        first, second = -1, -1
        count = 0
        
        for start, end in intervals:
            if start <= first:
                continue
            elif start <= second:
                first = second
                second = end
                count += 1
            else:
                first = end - 1
                second = end
                count += 2
        
        return count

This implementation first sorts the intervals and initializes trackers for the last two numbers added. It iterates through each interval, checking coverage with the current first and second values. Depending on the overlap, it decides how many new numbers to add. This ensures minimal additions while satisfying the "at least two per interval" condition.

Go Solution

import "sort"

func intersectionSizeTwo(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        if intervals[i][1] == intervals[j][1] {
            return intervals[i][0] > intervals[j][0]
        }
        return intervals[i][1] < intervals[j][1]
    })
    
    first, second := -1, -1
    count := 0
    
    for _, interval := range intervals {
        start, end := interval[0], interval[1]
        if start <= first {
            continue
        } else if start <= second {
            first = second
            second = end
            count++
        } else {
            first = end - 1
            second = end
            count += 2
        }
    }
    
    return count
}

The Go solution mirrors the Python implementation. Sorting uses sort.Slice with a custom comparator. The main difference is Go syntax, such as the for loop over slices and tuple unpacking replacement.

Worked Examples

Example 1: [[1,3],[3,7],[8,9]]

  1. Sort → [[1,3],[3,7],[8,9]]
  2. Initialize first=-1, second=-1, count=0
  3. Interval [1,3] → neither first nor second inside → add 2,3, update first=2, second=3, count=2
  4. Interval [3,7] → only second=3 inside → add 7, update first=3, second=7, count=3
  5. Interval [8,9] → neither inside → add 8,9, update first=8, second=9, count=5

Final result: 5

Example 2: [[1,3],[1,4],[2,5],[3,5]]

  1. Sorted: [[1,3],[1,4],[2,5],[3,5]]
  2. Interval [1,3] → add 2,3, count=2
  3. Interval [1,4] → both numbers in interval? 2,3 → yes, nothing to add
  4. Interval [2,5] → 2,3 in interval → yes, nothing to add
  5. Interval [3,5] → 2,3 → only second in interval? yes → add 5, count=3

Result: 3

Example 3: [[1,2],[2,3],[2,4],[4,5]]

  1. Sorted: [[1,2],[2,3],[2,4],[4,5]]
  2. [1,2] → add 1,2, count=2
  3. [2,3] → only second=2 inside → add 3, count=3
  4. [2,4] → only second=3 inside → add 4, count=4
  5. [4,5] → only second=4 inside → add 5, count=5

Result: 5

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates, iterating through intervals is O(n)
Space O(1) Only a constant number of variables are used aside from input

Sorting ensures intervals are processed optimally, and tracking only the last two numbers keeps memory usage minimal.

Test Cases

# Provided examples
assert Solution().intersectionSizeTwo([[1,3],[3,7],[8,9]]) == 5  # basic intervals
assert Solution().intersectionSizeTwo([[1,3],[1,4],[2,5],[3,5]]) == 3  # overlapping intervals
assert Solution().intersectionSizeTwo([[1,2],[2,3],[2,4],[4,5]]) == 5  # consecutive intervals

# Edge cases
assert Solution().intersectionSizeTwo([[0,1]]) == 2  # minimal interval, must include both
assert Solution().intersectionSizeTwo([[0,10**8]]) == 2  # very large interval, still only need last two
assert Solution().intersectionSizeTwo([[1,3],[2,5],[4,6]]) == 4  # overlapping, need careful selection
assert Solution().intersectionSizeTwo([[1,2],[3,4],[5,6]]) == 6  # non-overlapping, must add all

| Test | Why |

|