986. Interval List Intersections

when deciding which list to advance, we should compare the 2nd element in list instead of the 1st one. We are evaluating which range could have impact on the rest.

approach 1: merge

class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        i, j = 0, 0
        res = []
        while i < len(firstList) and j < len(secondList):
            left = max(firstList[i][0], secondList[j][0])
            right = min(firstList[i][1], secondList[j][1])
            if left <= right:
                res.append([left, right])
            
            if firstList[i][1] <= secondList[j][1]:
                i += 1
            else:
                j += 1
            
        return res

approach 2: select smaller one

def merge_intervals(intervals1, intervals2):
    merged_intervals = []
    i, j = 0, 0
    
    # Helper function to add an interval to the merged list
    def add_interval(interval):
        if not merged_intervals:
            merged_intervals.append(interval)
        else:
            last_interval = merged_intervals[-1]
            if interval[0] <= last_interval[1]:  # Overlapping intervals
                merged_intervals[-1] = [last_interval[0], max(last_interval[1], interval[1])]
            else:
                merged_intervals.append(interval)
    
    # Step 2: Traverse both lists and merge intervals
    while i < len(intervals1) and j < len(intervals2):
        if intervals1[i][0] < intervals2[j][0]:
            add_interval(intervals1[i])
            i += 1
        else:
            add_interval(intervals2[j])
            j += 1
    
    # Append remaining intervals from intervals1
    while i < len(intervals1):
        add_interval(intervals1[i])
        i += 1
    
    # Append remaining intervals from intervals2
    while j < len(intervals2):
        add_interval(intervals2[j])
        j += 1
    
    return merged_intervals

followup: merge k interval list

option 1: use pq to pick next one to add
option 2: divide and conquer - slit to 2 halves, and merge each of them, then merge the final 2 lists

986. Interval List Intersections - cocoder39/coco39_LC GitHub Wiki