59. Insert Interval - Calendar Management

You're building a calendar feature that needs to insert a new time interval into a sorted list of non-overlapping intervals. This is useful for calendar scheduling and time management.

You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represent the start and the end of the ith interval and intervals is sorted in ascending order by start_i. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by start_i and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Requirements

1. Basic Functionality

• Insert new interval into sorted intervals
• Merge overlapping intervals
• Maintain sorted order
• Return updated intervals array

Example Usage

insert([[1,3],[6,9]], [2,5]); // [[1,5],[6,9]]
// Insert [2,5] merges with [1,3] to form [1,5]

insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8]); 
// [[1,2],[3,10],[12,16]]
// Insert [4,8] merges with [3,5], [6,7], and [8,10]

Real-World Context

This problem models real calendar scenarios:

• Calendar scheduling: Insert new meeting time
• Time slot management: Add new time slot
• Interval management: Merge overlapping intervals
• Event scheduling: Insert and merge events