DSA Patterns Made Simple · Linked Lists, Stacks and Intervals
Intervals: Sort, Then Sweep
Meetings, bookings and time ranges: sort by start time, then walk through once, merging or comparing neighbours. One idea solves merging, inserting and 'can I attend every meeting?'.
The problem
Merge Intervals: a calendar has busy blocks [1,3], [2,6], [8,10], [15,18]. Which time ranges are busy, as few blocks as possible? Answer: [1,6], [8,10], [15,18].
Comparing every pair of blocks is O(n²), and overlaps can chain. Sorted by start time, though, overlaps can only happen between neighbours.
How to spot it
- Input is a list of [start, end] pairs: meetings, bookings, ranges, timestamps
- "Merge overlapping", "insert a new interval", "can a person attend all meetings?"
- "Minimum number of rooms", "remove the fewest intervals so none overlap"
The idea
- Sort by start.
- Sweep left to right, keeping the current merged block. If the next interval starts before (or exactly when) the current one ends, they overlap: extend the end to the later of the two ends. Otherwise, close the current block and start a new one.
Two intervals [a, b] and [c, d] (with a ≤ c after sorting) overlap when c <= b.
For "how many rooms", sweep start and end times separately: a start needs a room, an end frees one; the most rooms in use at once is the answer.
The template
intervals.sort(key=lambda iv: iv[0])
merged = []
for start, end in intervals:
if merged and start <= merged[-1][1]: # overlaps the last block
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
intervals.sort((a, b) => a[0] - b[0]);
const merged = [];
for (const [start, end] of intervals) {
if (merged.length && start <= merged.at(-1)[1]) { // overlaps the last block
merged.at(-1)[1] = Math.max(merged.at(-1)[1], end);
} else {
merged.push([start, end]);
}
}
Worked example
Merge overlapping blocks, check whether one person can attend every meeting, and count the meeting rooms needed.
def merge(intervals):
merged = []
for start, end in sorted(intervals):
if merged and start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
def can_attend_all(meetings):
meetings = sorted(meetings)
return all(meetings[i][0] >= meetings[i - 1][1] for i in range(1, len(meetings)))
def rooms_needed(meetings):
starts = sorted(s for s, _ in meetings)
ends = sorted(e for _, e in meetings)
rooms = best = 0
e = 0
for s in starts:
while ends[e] <= s: # meetings that ended by now free their rooms
rooms -= 1
e += 1
rooms += 1
best = max(best, rooms)
return best
print(merge([[1, 3], [2, 6], [8, 10], [15, 18]]))
print(merge([[1, 4], [4, 5]]))
print("attend all?", can_attend_all([[0, 30], [5, 10], [15, 20]]))
print("attend all?", can_attend_all([[7, 10], [2, 4]]))
print("rooms:", rooms_needed([[0, 30], [5, 10], [15, 20]]))
Output
[[1, 6], [8, 10], [15, 18]] [[1, 5]] attend all? False attend all? True rooms: 2
function merge(intervals) {
const merged = [];
for (const [start, end] of [...intervals].sort((a, b) => a[0] - b[0])) {
if (merged.length && start <= merged.at(-1)[1]) merged.at(-1)[1] = Math.max(merged.at(-1)[1], end);
else merged.push([start, end]);
}
return merged;
}
function canAttendAll(meetings) {
const m = [...meetings].sort((a, b) => a[0] - b[0]);
return m.every((iv, i) => i === 0 || iv[0] >= m[i - 1][1]);
}
function roomsNeeded(meetings) {
const starts = meetings.map(([s]) => s).sort((a, b) => a - b);
const ends = meetings.map(([, e]) => e).sort((a, b) => a - b);
let rooms = 0, best = 0, e = 0;
for (const s of starts) {
while (ends[e] <= s) { rooms--; e++; } // meetings that ended by now free their rooms
rooms++;
best = Math.max(best, rooms);
}
return best;
}
const show = (v) => JSON.stringify(v).replaceAll(",", ", ");
const py = (b) => (b ? "True" : "False");
console.log(show(merge([[1, 3], [2, 6], [8, 10], [15, 18]])));
console.log(show(merge([[1, 4], [4, 5]])));
console.log("attend all?", py(canAttendAll([[0, 30], [5, 10], [15, 20]])));
console.log("attend all?", py(canAttendAll([[7, 10], [2, 4]])));
console.log("rooms:", roomsNeeded([[0, 30], [5, 10], [15, 20]]));
Output
[[1, 6], [8, 10], [15, 18]] [[1, 5]] attend all? False attend all? True rooms: 2
Common mistakes
- Not sorting first. The whole pattern depends on start order.
- JavaScript's default sort.
array.sort()without a comparator sorts as strings ([10, 9]stays[10, 9]). Always pass(a, b) => a[0] - b[0]. - Touching intervals. Decide whether
[1,4]and[4,5]overlap (merging usually says yes; meetings that end at 4 and start at 4 usually don't clash). Read the problem. - Replacing instead of extending the end. Use
max(current end, new end):[1,10]followed by[2,3]must stay[1,10].
Practice
- Merge Intervals (medium)
- Insert Interval (medium): add everything that ends before the new one, merge everything that overlaps it, then add the rest.
Key points
- Sort by start, then one sweep: overlap if
next.start <= current.end. - Extend with
maxof the ends. - Rooms needed = the most meetings in progress at once (sweep sorted starts and ends).
- Cost is dominated by sorting: O(n log n).
Practice questions
After sorting by start, when do two intervals overlap?
Answer
When the next interval's start is less than or equal to the current interval's end (or strictly less, if touching intervals don't count as overlapping in the problem).
How do you find the minimum number of meeting rooms?
Answer
Sort start times and end times separately. Walk the starts; before each start, release rooms for meetings that have already ended (end ≤ start). Track the maximum rooms in use. O(n log n).
Open in the app to mark lessons complete, take notes and track your progress.