Intervals
Three phases in one pass
When something is inserted or removed, the list splits into before, touching, and after.
Key idea
The structure of the answer
Given a sorted list of non-overlapping intervals and one new interval to combine with them, the existing intervals fall into exactly three groups, in order: those entirely before the new one, those that touch it, and those entirely after.
The first group is copied through unchanged. The second group collapses into a single interval together with the new one. The third group is copied through unchanged. Writing the loop as three explicit phases rather than one loop with branches is clearer and much easier to get right.
The same structure, removing instead of adding
Here is the three-phase shape on a different task: removing a range from a set of intervals. The middle phase now splits intervals rather than merging them.
Tip
One interval can produce two
The second example shows why the two if statements are separate rather than an if-else: a cut strictly inside an interval leaves remnants on both sides, so both conditions fire and the interval becomes two.
Whenever a transformation can produce zero, one, or two outputs from one input, independent conditions are the shape you want. An if-else silently caps you at one.
Why it works
The middle phase when adding
For insertion the middle phase runs the other way. While the current interval touches the growing new one, absorb it: the start becomes the smaller of the two starts and the end the larger of the two ends.
The new interval keeps growing as it swallows more, which is why the loop condition has to be checked against the updated interval rather than the original. An insertion that spans several existing intervals collapses all of them into one, and that only works if each comparison uses the current merged bounds.
Tip
No sort needed
The input is already sorted and non-overlapping, so this is a genuinely linear algorithm, O(n) time. That is worth stating, because most problems in this unit pay for a sort and this one does not.
If you find yourself sorting here, reread the problem statement. The guarantee is doing work for you and discarding it costs a factor of log n for nothing.
Which comparison ends the middle phase?
You are inserting a new interval and absorbing everything it touches. Which condition means the current interval should be absorbed rather than copied through?
Insert Interval
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.