Problem statement

https://leetcode.com/problems/set-intersection-size-at-least-two/

Solution 1

The idea is to sort intervals by ends. Let us call our set S nails: so the goal is to use minimum number of nails such that each interval is nailed twice. When we sort intervals by ends, it is always more efficient to take the right end y of current interval [x, y] and if we need more points y - 1. Why? Because if we choose some point z < y-1 and it nails some other interval, point y-1 or y will nail it as well.

Let us also keep filled array, where we count how many times each interval is nailed. If it is already nailed 2 times or more, we just skip it. If it is nailed 0 times, we need to add two nails and we also update all counters for other intervals. If it nailed 1 time, we add one nail.

Complexity

Time complexity of this approach is O(n^2), because for each interval we traverse all other intervals in O(n). Space complexity is O(n).

Code

class Solution:
    def intersectionSizeTwo(self, intervals):
        n, nails = len(intervals), 0
        filled = [0] * n
        intervals.sort(key = lambda x: (x[1], -x[0]))
        for i, (x, y) in enumerate(intervals):
            nails += max(0, 2-filled[i])
            
            for k in range(2-filled[i]):
                for j in range(n): filled[j] += intervals[j][0] <= y-k
            
        return nails

Solution 2

Actually, we can implement the same logic with O(n log n) complexity if we keep positions of our nails (elements in S). When we have new interval, we need to check if we already have nails in it: and we need to add 0, 1 or 2 new nails.

Complexity

Time complexity is O(n log n), space complexity is O(n).

Code

class Solution:
    def intersectionSizeTwo(self, intervals):
        intervals.sort(key = lambda x:(x[1], -x[0])) 
        nails = [-2,-1]
        for x, y in intervals:
            q = bisect_left(nails[-2:], x)
            for i in range(q-1,-1,-1): nails.append(y-i)

        return len(nails) - 2