1229. Meeting Scheduler

class Solution:
    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:
        """
        tc O((M+N)lg(M+N))
        sc  O(M+N)
        main idea: use one list to store all time slots, tracking accumulating cnt and cache previous start time 
        1. append both slots' start and end time into list with change mark 1/ 0
        2. sort by time and by start then end 
        3. each time start point, cnt + 1; otherwise cnt - 1;   
           chekc available time only when current event is end and previous cnt == 2   
        """
        l = []
        for s,e in slots1:
            l.append((s,1))
            l.append((e,0))
        for s,e in slots2:
            l.append((s,1))
            l.append((e,0))
        l.sort()
        cnt,start = 0,0
        for t,v in l:
            if v == 1:
                cnt += 1
                start = t
            else:
                if cnt == 2:
                    if t - start >= duration:
                        return [start,start+duration]
                cnt -= 1
        return []
################
class Solution:
    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:
        """
        main idea is to check accumutive sum's peek time and compare its end time with previous time 
        """
        d = defaultdict(int)
        for s,e in slots1:
            d[s] += 1
            d[e] -= 1 
        for s,e in slots2:
            d[s] += 1
            d[e] -= 1
        cnt = 0
        tm = sorted(d.items())
        prev_end = tm[0][0] 
        for t,v in tm:
            if cnt == 2 and cnt + v < 2: # here to prevent cases where two intervals totally overlaps 
                gap = t - prev_t
                if gap >= duration:
                    return [prev_t,prev_t+duration]
            cnt += v
            prev_t = t
        return []

class Solution:
    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:
        """ tc O((M+N)log(M+N))  sc O(N+M)
        """
        # filter out  time slots not meeting the min diff >= duration 
        timeslots = list(filter(lambda x: x[1] - x[0] >= duration, slots1 + slots2))
        #print(timeslots)
        heapq.heapify(timeslots)

        while len(timeslots) > 1:
            start1, end1 = heapq.heappop(timeslots) # t1 must <= t2
            start2, end2 = timeslots[0]
            if end1 >= start2 + duration:
                return [start2, start2 + duration]
        return []

class Solution:
    def minAvailableDuration(self, A: List[List[int]], B: List[List[int]], duration: int) -> List[int]:
        """
        tc O(NlgN+MlgM)  sc O(1)
        """
        A.sort()
        B.sort()
        n1,n2,p1,p2 = len(A),len(B),0,0
        while p2 < n2 and p1 < n1:
            # get overlap invertal  point 
            start = max(A[p1][0],B[p2][0])
            end = min(A[p1][1],B[p2][1])
            if end - start >= duration : # filter out non-overlap cases 
                # find answer 
                return [start,start+duration]
            # move p1 or p2 by comparing end time 
            elif A[p1][1] < B[p2][1]:
                p1 += 1
            elif A[p1][1] >= B[p2][1]:
                p2 += 1
        return []