Set Intersection Size At Least Two - Leetcode Solution

The Set Intersection Size At Least Two problem on LeetCode can be solved using the Greedy approach. The problem can be restated as follows:

Given a set of intervals, find the minimum number of elements required to be present in every interval such that the intersection of all the intervals has a size of at least two.

To solve the problem, we can follow the following steps:

1. Sort the intervals based on their end points.

2. Assign two variables, last and secondLast, to keep track of the last two elements of the minimum-sized intersection we must create. Initially, last can be set to -1 and secondLast can be set to -2.

3. Iterate over each interval in sorted order. Let's use the variable curr to represent the current interval.

4. If curr[0] > last, it means that the current interval does not overlap with the minimum-sized intersection we have created so far. In this case, we need to add both curr[1] - 1 and curr[1] to the minimum-sized intersection, and update last and secondLast accordingly.

5. Otherwise, if curr[0] <= last, it means that the current interval overlaps with the minimum-sized intersection. In this case, we only need to add curr[1] to the minimum-sized intersection.

6. Our final result will be the size of the minimum-sized intersection.

Here's the Python code implementing this algorithm:

def intersectionSizeTwo(intervals):
    intervals.sort(key=lambda x: x[1])
    last, secondLast = -1, -2
    result = 0
    for curr in intervals:
        if curr[0] > last:
            result += 2
            secondLast, last = last, curr[1] - 1
        elif curr[0] <= secondLast:
            continue
        else:
            result += 1
            secondLast, last = last, curr[1]
    return result

The time complexity of this algorithm is O(n log n), where n is the number of intervals, due to the sorting operation. The space complexity is O(1), as we only need constant space to store our variables.

1