Insert Interval: Three Phases

Concepts: pyInsertInterval, pyThreePhase

Insert interval is merge intervals with a twist: the existing list is already sorted and non-overlapping. You are given one new interval to insert in the right place and merge any conflicts. The key insight is that the problem has exactly three phases, and if you code them as three explicit phases, the solution is clean and obvious. If you try to handle everything in one loop with a pile of conditionals, you will make a mistake. The Three Phases The elegance here is the separation of concerns. Phase 1 and Phase 3 do not think about the new interval at all — they just copy. Phase 2 does nothing but expand the new interval's boundaries. Three while loops, each with a single condition. No nested ifs. No flags. No special case for 'the new interval goes at the beginning' or 'at the end' — thos