Practice/FanDuel/Leetcode 57. Insert Interval

Leetcode 57. Insert Interval

CodingMust

Problem

You are building a calendar system that manages meeting time slots. Given a collection of non-overlapping time intervals that are already sorted by their start times, insert a new time interval into this collection. After insertion, merge any overlapping intervals to ensure the final collection remains sorted and contains no overlaps.

Each interval is represented as a pair of integers [start, end] where start is the beginning time and end is the ending time of the interval.

Requirements

1. The input intervals are sorted by start time and do not overlap with each other
2. Insert the new interval into the correct position
3. Merge all overlapping intervals after insertion
4. Return the resulting list of non-overlapping intervals in sorted order
5. The solution should handle edge cases like empty input or the new interval encompassing all existing intervals

Constraints

• 0 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= start_i < end_i <= 10^6
• intervals is sorted by start_i in ascending order
• newInterval.length == 2
• 0 <= newInterval[0] < newInterval[1] <= 10^6

Examples

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]] Explanation: The new interval [2,5] overlaps with [1,3], so they merge into [1,5]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] Output: [[1,2],[3,10],[12,16]] Explanation: The interval [4,8] overlaps with [3,5], [6,7], and [8,10], merging them all

Example 3:

Input: intervals = [], newInterval = [5,7] Output: [[5,7]] Explanation: With no existing intervals, return just the new interval