Interview Questions

1. Merge Intervals

   coding

   Practice

   Title: Merge Overlapping Intervals

   Problem: Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

   Function Signature: def merge(intervals: List[List[int]]) -> List[List[int]]

   Input: intervals: list of pairs [start, end]

   Output: list of merged intervals sorted by start time

   Sample Input: intervals = [[1,3],[2,6],[8,10],[15,18]]

   Sample Output: The intervals [1,3] and [2,6] overlap, so they merge into [1,6].

   Example: 1 <= len(intervals) <= 10^4; 0 <= start_i <= end_i <= 10^4.

   Constraints: Sort the intervals by start time and iterate, merging intervals when they overlap.

   Hints: Sort the intervals by start time and iterate, merging intervals when they overlap.

   Follow-up: How would you modify the algorithm if the input intervals are already sorted? Could you handle inserting a new interval into an existing sorted list?