38. Interval Scheduling

Medium

Topics

Helpful tools to learn & understand

Visualize LogicActive Simulator

Watch key transitions, pointers, and variables update step-by-step.

Open

Check Solutions

Read clean, documented implementations across multiple patterns.

View Code

Thinkpad (Draw & Note)

Sketch diagrams on an infinite canvas and draft notes directly inline.

Draw

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], merging them into [1,5]. [6,9] remains unchanged.

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 new interval [4,8] overlaps with [3,5], [6,7], and [8,10], merging them into [3,10]. [1,2] and [12,16] remain unchanged.

Example 3:

Input: intervals = [], newInterval = [5,7]

Output: [[5,7]]

Explanation: Since the intervals array is empty, the new interval [5,7] is simply added as the first element.

Example 4:

Input: intervals = [[1,5]], newInterval = [2,3]

Output: [[1,5]]

Explanation: The new interval [2,3] is completely contained within [1,5], so they are merged into [1,5].

Example 5:

Input: intervals = [[1,5]], newInterval = [0,0]

Output: [[0,0],[1,5]]

Explanation: The new interval [0,0] comes before [1,5] and does not overlap, so it is inserted at the beginning.

Constraints:

Time Complexity

O(n log n)

Space Complexity

O(1)