You are given sorted, non-overlapping intervals and one new interval. Insert it, and merge where needed, so the list stays sorted and non-overlapping.
DSA Animator › DSA Revision › Intervals › Insert Interval
Remember: before, overlapping, after. Three simple loops, and no sorting. The video solves Insert Interval (LeetCode 57, Medium) with the Three-Phase Scan pattern from the Intervals topic, and you can replay every step in the interactive Insert Interval animation.
You are given sorted, non-overlapping intervals and one new interval. Insert it, and merge where needed, so the list stays sorted and non-overlapping.
For 1 to 2, 3 to 5, 6 to 7, 8 to 10 and 12 to 16, inserting 4 to 8 gives 1 to 2, 3 to 10 and 12 to 16.
You could append the new interval, sort everything, and run merge intervals. But the list is already sorted, so one linear scan is enough.
First, copy every interval that ends before the new one starts. Then, while intervals start before the new one ends, merge them into it by widening its start and end. Finally, add the merged interval and copy everything after it.
1 to 2 ends before 4, so copy it. 3 to 5 overlaps, so the new interval grows to 3 to 8. 6 to 7 is inside, and 8 to 10 touches it, so it grows to 3 to 10. 12 starts after 10, so add 3 to 10, then copy 12 to 16. The result is 1 to 2, 3 to 10 and 12 to 16.
In code, the first loop copies intervals whose end is less than the new start. The second loop takes the minimum start and the maximum end of every overlapping interval. The third loop copies the rest. It's O of n time.
Remember: before, overlapping, after. Three simple loops, and no sorting.