757. Set Intersection Size At Least Two

[mah-shamim]

Topics: Array, Greedy, Sorting, Weekly Contest 65

You are given a 2D integer array intervals where intervals[i] = [startᵢ, endᵢ] represents all the integers from startᵢ to endᵢ 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 <= startᵢ < endᵢ <= 10⁸

[mah-shamim]

We need to find the smallest set of numbers that contains at least two elements from each given interval.

The key insight is to sort the intervals by their end points and use a greedy approach to select numbers that will cover as many intervals as possible.

Approach:

1. Sort intervals by end point (ascending), and if end points are equal, sort by start point (descending)
2. Maintain two variables to track the last two numbers selected
3. For each interval:
   • If it already contains both last selected numbers, skip it
   • If it contains only one of them, add the largest number from the current interval
   • If it contains none of them, add the two largest numbers from the current interval

Let's implement this solution in PHP: 757. Set Intersection Size At Least Two

<?php
/**
 * @param Integer[][] $intervals
 * @return Integer
 */
function intersectionSizeTwo($intervals) {
    // Sort intervals by end point, and by start point descending if ends are equal
    usort($intervals, function($a, $b) {
        if ($a[1] == $b[1]) {
            return $b[0] - $a[0];
        }
        return $a[1] - $b[1];
    });

    $size = 0;
    $first = -1;
    $second = -1;

    foreach ($intervals as $interval) {
        $start = $interval[0];
        $end = $interval[1];

        // If current interval already has at least two elements from our set
        if ($first >= $start && $second >= $start) {
            continue;
        }

        // If current interval has only one element from our set
        if ($second >= $start) {
            $first = $second;
            $second = $end;
            $size += 1;
        }
        // If current interval has no elements from our set
        else {
            $first = $end - 1;
            $second = $end;
            $size += 2;
        }
    }

    return $size;
}

// Test cases
echo intersectionSizeTwo([[1,3],[3,7],[8,9]]) . "\n";                                   // Output: 5
echo intersectionSizeTwo([[1,3],[1,4],[2,5],[3,5]]) . "\n";                             // Output: 3
echo intersectionSizeTwo([[1,2],[2,3],[2,4],[4,5]]) . "\n";                             // Output: 5
echo intersectionSizeTwo([[5,10]]) . "\n";                                              // Output: 2
echo intersectionSizeTwo([[1,2],[4,5],[7,8]]) . "\n";                                   // Output: 6
echo intersectionSizeTwo([[1,10],[2,9],[3,8],[4,7]]) . "\n";                            // Output: 2
echo intersectionSizeTwo([[1,5],[3,7],[6,9]]) . "\n";                                   // Output: 4
echo intersectionSizeTwo([[2,6],[2,4],[2,7],[2,10]]) . "\n";                            // Output: 2
echo intersectionSizeTwo([[3,8],[5,8],[1,8]]) . "\n";                                   // Output: 2
echo intersectionSizeTwo([[1,2],[2,3],[3,4],[4,5]]) . "\n";                             // Output: 4
echo intersectionSizeTwo([[1,100],[2,99],[3,98],[4,97],[80,120],[85,130]]) . "\n";      // Output: 2
echo intersectionSizeTwo([[1,5],[1,4],[1,3],[1,2],[4,6]]) . "\n";                       // Output: 3
echo intersectionSizeTwo([[1,10],[20,30],[40,60]]) . "\n";                              // Output: 6
echo intersectionSizeTwo([[5,9],[5,9],[5,9],[5,9]]) . "\n";                             // Output: 2
echo intersectionSizeTwo([[1,4],[2,6],[4,8],[7,9],[8,11]]) . "\n";                      // Output: 4
echo intersectionSizeTwo([[1,1000],[50,51],[51,200],[600,601]]) . "\n";                 // Output: 4
echo intersectionSizeTwo([[1,3],[2,4],[3,5],[4,6],[5,7]]) . "\n";                       // Output: 4
echo intersectionSizeTwo([[1,2],[1,3],[2,3],[2,4]]) . "\n";                             // Output: 3
?>

Explanation:

1. Sorting: We sort intervals primarily by their end points. When end points are equal, we sort by start points in descending order. This ensures that wider intervals (with smaller start points) come after narrower ones when they end at the same point.

2. Greedy Selection: We maintain first and second to represent the two most recently added numbers to our set.

3. Processing Intervals:

   • If both first and second are within the current interval, we're already covered.
   • If only second is within the interval, we add the current interval's end point (the largest possible number that can help cover future intervals).
   • If neither is within the interval, we add the two largest numbers from the current interval (end-1 and end).

4. Why it works: By always selecting the largest possible numbers from each interval, we maximize the chance that these numbers will also cover subsequent intervals, thus minimizing the total set size.

Time Complexity: O(n log n) due to sorting
Space Complexity: O(1) excluding the space needed for sorting

[topugit]

Thanks for solving the problem of "Set Intersection Size At Least Two"

[mah-shamim]

Thanks