Clinic #28: Merge Intervals

A board drawn in Hinglish for a problem about booking meeting rooms: bars laid along a timeline, each one a stretch from a start to an end. This lesson asks those same bars a different question, and the board’s panel on spotting the pattern already files it under “sort by start”.

Before you start. Sorting a list takes a little more than one pass over it: ten times the items costs about thirteen times the work, which engineers write as O(n log n), and Sorting & Searching shows where that comes from. Reading every item once is O(n), and reading every pair of items is O(n²), which at ten thousand items is fifty million pairs.