Insert an Interval — Solution & Editorial

Back to the Problem

Emit intervals ending strictly before the new one; absorb every interval that overlaps or touches it (expanding its ends); then emit it followed by the untouched rest.

Complexity: O(N)