Problem statement

https://leetcode.com/problems/reformat-department-table/

Solution

One way to solve this problem is to sort intervals by its ends, keeping two events: +1 for opening and -1 for closing. Then we iterate through events and when we meet cnt == 2 and event == 1, it means that we meet end of intersections segment, we check if its length is more or equal than target. If we have cnt == 1 and event == 1, it means that we have start of intersection segment, so we add it to ints`.

Complexity

Time complexity is O(n log n), where n is total number of all intervals, space complexity is O(n).

Code

class Solution:
    def minAvailableDuration(self, S1, S2, D):
        P  = [[x, 1] for x, _ in chain(S1, S2)]
        P += [[y, -1] for _, y in chain(S1, S2)]
        P = sorted(P)
        
        cnt, ints = 0, []
        
        for coord, event in P:
            if cnt == 2 and event == -1: 
                if coord - ints[-1] >= D: return [ints[-1], ints[-1] + D] 
            if cnt == 1 and event == 1: ints += [coord]
            cnt += event
            
        return []