# Set Intersection Size At Least Two
**Difficulty:** HARD
[External](https://leetcode.com/problems/set-intersection-size-at-least-two)
Canonical: https://scaleengineer.com/dsa/problems/set-intersection-size-at-least-two
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [DP world](https://scaleengineer.com/companies/dp-world)
---
## Problem
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`

# Approaches
## Greedy Approach with Naive Point Counting
This approach uses a greedy strategy. The core idea is to process intervals in an order that allows us to make locally optimal choices that lead to a globally optimal solution. By sorting the intervals by their end points, we deal with the intervals that 'finish' earliest first. When we are forced to add points to satisfy an interval, we choose points at the very end of that interval. This maximizes the chance that these new points will also help satisfy subsequent intervals.

This specific implementation uses a straightforward but inefficient method to check how many points an interval contains: it iterates through the entire list of points chosen so far for each interval.
**Time:** O(N^2). Sorting takes O(N log N). The main loop iterates through N intervals. Inside the loop, we scan the list of chosen points, which can grow up to O(N) in size. This results in a total time complexity of O(N^2). · **Space:** O(N), where N is the number of intervals. In the worst case, the containing set `S` can have up to 2N points.
**Pros:** The greedy choice is intuitive once the intervals are sorted.; The implementation is conceptually straightforward, directly translating the greedy logic without complex state tracking.
**Cons:** The time complexity is quadratic, which can be too slow for larger inputs (N=3000 could lead to ~9 million operations in the main loop).
### Explanation
The algorithm begins by sorting the input `intervals` based on their end points. This is a crucial step in the greedy strategy. We then initialize a list, let's call it `S`, which will store the integers of our resulting containing set.

We iterate through the sorted intervals one by one. For each interval `[start, end]`, we determine how many points from our set `S` are already contained within it. This is done by a simple linear scan through `S`.

- If the count of contained points is zero, we need to add two new points. The greedy choice is to add `end` and `end - 1` to `S`. This is because these points satisfy the current interval's requirement while being as large as possible, which makes them more likely to be part of subsequent intervals (which will have end points greater than or equal to the current `end`).
- If the count is one, we only need one more point. We add `end` to `S` for the same reason.
- If the count is two or more, the condition for the current interval is already met, and we proceed to the next one without adding any points.

After iterating through all the intervals, the size of `S` gives us the minimum size of the containing set.

```java
import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int intersectionSizeTwo(int[][] intervals) {
        // Sort intervals by end point ascending, then by start point descending
        Arrays.sort(intervals, (a, b) -> {
            if (a[1] != b[1]) {
                return a[1] - b[1];
            } else {
                return b[0] - a[0];
            }
        });

        List<Integer> points = new ArrayList<>();

        for (int[] interval : intervals) {
            int start = interval[0];
            int end = interval[1];

            int count = 0;
            // Naive check: iterate through all chosen points
            for (int p : points) {
                if (p >= start && p <= end) {
                    count++;
                }
            }

            if (count == 0) {
                points.add(end - 1);
                points.add(end);
            } else if (count == 1) {
                // Find which point is missing. We need to add the largest possible one.
                // The greedy choice is always to add 'end'.
                // To avoid duplicates, we can check if 'end' is already there.
                // A simpler logic that works is to just add 'end' and rely on the fact
                // that the single point already in the interval must be less than 'end'.
                // Let's refine the logic to be more robust.
                int last = points.size() - 1;
                if (points.get(last) < start) { // The existing point is outside
                    points.add(end);
                } else { // The existing point is inside, add 'end' if not already present
                    // The greedy logic is to just add 'end'.
                    // Let's trace: if points has [2,3] and interval is [3,7], count is 1.
                    // We add 7. points becomes [2,3,7]. Correct.
                    // If points has [2,5] and interval is [3,5], count is 1.
                    // We add 5. But 5 is already there. This logic is tricky.
                    // The optimized approach avoids this complexity.
                    // A simpler version of this O(N^2) approach:
                    points.add(end);
                }
            }
        }
        
        // The above logic for count==1 is complex. A cleaner O(N^2) is:
        List<Integer> s = new ArrayList<>();
        for (int[] inv : intervals) {
            int start = inv[0];
            int end = inv[1];
            int c = 0;
            for (int p : s) {
                if (p >= start) {
                    c++;
                }
            }
            if (c == 0) {
                s.add(end - 1);
                s.add(end);
            } else if (c == 1) {
                s.add(end);
            }
            // We need to sort s for the next iteration's check to be efficient,
            // but that complicates it. The optimized approach is much cleaner.
            // The core idea of O(N^2) is the nested loop, which is what we are demonstrating.
        }
        // The logic becomes complex. The optimized version is the standard one.
        // For a working O(N^2) code, we can use the logic from the optimized version
        // but replace the p1, p2 check with a list scan.
        List<Integer> finalSet = new ArrayList<>();
        for (int[] interval : intervals) {
            int start = interval[0];
            int end = interval[1];
            int needed = 2;
            // Scan from the end of the list for efficiency
            for (int i = finalSet.size() - 1; i >= 0; i--) {
                if (finalSet.get(i) >= start) {
                    needed--;
                    if (needed == 0) break;
                }
            }
            if (needed == 2) {
                finalSet.add(end - 1);
                finalSet.add(end);
            } else if (needed == 1) {
                finalSet.add(end);
            }
        }
        return finalSet.size();
    }
}
```
### Algorithm
1. Sort the `intervals` array based on their end points in ascending order.
2. Initialize an empty list, `S`, to store the points of our containing set.
3. Iterate through each sorted interval `[start, end]`.
4. For each interval, iterate through the points currently in `S` to count how many of them fall within `[start, end]`. Let this be `c`.
5. If `c` is 0, the interval is completely uncovered. We must add two points. To be efficient for future intervals, we greedily pick the two largest possible integers, `end - 1` and `end`, and add them to `S`.
6. If `c` is 1, the interval is partially covered. We need one more point. We greedily pick the largest possible integer, `end`, and add it to `S`.
7. If `c` is 2 or more, the interval is already satisfied, and we do nothing.
8. After checking all intervals, the final size of the list `S` is the minimum possible size of a containing set.

## Optimized Greedy Approach
This is an optimized version of the greedy approach. It relies on the same principle: sort intervals by their end points and add points greedily from the end of an interval when needed. The key optimization is realizing that after sorting, to check if the current interval is satisfied, we only need to consider the most recently added points. Specifically, because we always add the largest possible numbers (`end` and `end-1`), we only need to track the two largest numbers chosen so far (`p1` and `p2`) to make a decision for the current interval. This avoids the costly O(N) scan of all chosen points for each interval, reducing the check to an O(1) operation.
**Time:** O(N log N), where N is the number of intervals. The sorting step takes O(N log N), and the subsequent loop over the intervals takes O(N) time, as each step inside the loop is a constant time operation. · **Space:** O(log N) or O(N) for sorting, depending on the language's sort implementation. The algorithm itself only uses O(1) extra space for variables.
**Pros:** Highly efficient with a time complexity dominated by sorting.; Optimal space complexity, using only a few variables to track state.
**Cons:** The logic of tracking and updating the two largest points (`p1`, `p2`) can be slightly less intuitive than maintaining a full list of points.
### Explanation
The algorithm's efficiency comes from a clever observation. After sorting intervals by their end points, when we process an interval `[start, end]`, any points we have added so far must be less than or equal to `end`. To check if `[start, end]` is covered, we only care about points greater than or equal to `start`. Therefore, only the largest points we've added are relevant.

We maintain the two largest points added to our set, `p1 < p2`. For each interval `[start, end]`:
- If `start <= p1`, then `start <= p1 < p2`. Both points are in the interval. The requirement is met.
- If `start > p1` but `start <= p2`, only `p2` is in the interval. We need one more point. We add `end`. Our new two largest points are the old `p2` and the new `end`. So we update `p1 = p2` and `p2 = end`, and increment our total count.
- If `start > p2`, neither of our largest points are in the interval. No other smaller point could be in the interval either. We need to add two points. We choose `end-1` and `end`. We update `p1 = end - 1` and `p2 = end`, and increment our count by two.

This process ensures that at each step, we make a decision that satisfies the current interval while adding points that are most beneficial for the remaining intervals, all in constant time per interval.

```java
import java.util.Arrays;

class Solution {
    public int intersectionSizeTwo(int[][] intervals) {
        // Sort intervals by end point ascending, then by start point descending
        Arrays.sort(intervals, (a, b) -> {
            if (a[1] != b[1]) {
                return a[1] - b[1];
            } else {
                return b[0] - a[0];
            }
        });

        int count = 0;
        // p1 and p2 are the two largest numbers in our set S
        // Initialize them to a value smaller than any possible coordinate
        int p1 = -1;
        int p2 = -1;

        for (int[] interval : intervals) {
            int start = interval[0];
            int end = interval[1];

            // Case 1: The interval is already covered by p1 and p2
            // If start <= p1, since p1 < p2, both are in the interval.
            if (start <= p1) {
                continue;
            }

            // Case 2: The interval is covered by p2 but not p1
            // We need to add one more point.
            if (start <= p2) {
                count++;
                // The new point is 'end'. The previous p2 is now the smaller of the two largest.
                p1 = p2;
                p2 = end;
            } else { // Case 3: The interval is not covered by p1 or p2
                // We need to add two points.
                count += 2;
                p2 = end;
                p1 = end - 1;
            }
        }

        return count;
    }
}
```
### Algorithm
1. Sort the `intervals` array first by their end points in ascending order. If two intervals have the same end point, sort them by their start points in descending order.
2. Initialize a counter for the set size, `count = 0`. Also, initialize two variables, `p1` and `p2`, to -1. These will track the two largest integers chosen for our set so far.
3. Iterate through the sorted intervals `[start, end]`.
4. For each interval, check its overlap with the points `p1` and `p2`:
   a. If `start <= p1`, it means the interval contains both `p1` and `p2` (since `p1 < p2`). The interval is satisfied, so we continue to the next one.
   b. If `start > p1` but `start <= p2`, the interval is only covered by `p2`. We need one more point. We add `end` to our set, increment `count`, and update our largest points: `p1` becomes the old `p2`, and `p2` becomes `end`.
   c. If `start > p2`, the interval is not covered by any of our tracked points. We need two points. We add `end - 1` and `end` to our set, increment `count` by 2, and update `p1 = end - 1` and `p2 = end`.
5. After the loop finishes, `count` holds the minimum size of the containing set.

# Solutions
### Java

```java
class Solution {
public
  int intersectionSizeTwo(int[][] intervals) {
    Arrays.sort(intervals, (a, b)->a[1] == b[1] ? b[0] - a[0] : a[1] - b[1]);
    int ans = 0;
    int s = -1, e = -1;
    for (int[] v : intervals) {
      int a = v[0], b = v[1];
      if (a <= s) {
        continue;
      }
      if (a > e) {
        ans += 2;
        s = b - 1;
        e = b;
      } else {
        ans += 1;
        s = e;
        e = b;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int intersectionSizeTwo(vector<vector<int>> &intervals) {
    sort(intervals.begin(), intervals.end(),
         [&](vector<int> &a, vector<int> &b) {
           return a[1] == b[1] ? a[0] > b[0] : a[1] < b[1];
         });
    int ans = 0;
    int s = -1, e = -1;
    for (auto &v : intervals) {
      int a = v[0], b = v[1];
      if (a <= s)
        continue;
      if (a > e) {
        ans += 2;
        s = b - 1;
        e = b;
      } else {
        ans += 1;
        s = e;
        e = b;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int: intervals . sort(key=lambda x: (x[1], - x[0])) s = e = - 1 ans = 0 for a, b in intervals: if a <= s: continue if a > e: ans += 2 s, e = b - 1, b else: ans += 1 s, e = e, b return ans

```