Interview Questions

1. Merge Intervals

   coding

   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?