Not the exercise, just the two moves it needs, shown on a list of scores. sorted with a key orders by one part of each item, and result[-1] is always the most recent thing you decided to keep.
runs = [["ada", 9], ["grace", 4], ["ada", 7], ["linus", 4]]
by_score = sorted(runs, key=lambda run: run[1])
print(by_score) # -> [['grace', 4], ['linus', 4], ['ada', 7], ['ada', 9]]
print(runs[0]) # -> ['ada', 9] sorted() left the original alone
kept = []
for name, score in by_score:
if kept and kept[-1][1] == score: # same as the last one kept?
continue
kept.append([name, score])
print(kept) # -> [['grace', 4], ['ada', 7], ['ada', 9]]
- Sorting brings the neighbours together
After sorting, everything that could interact sits next to each other. That is what lets one pass replace comparing every pair.
- Only ever look back one step
kept[-1] is the item you are still building. Each new item either changes it or starts a new one; nothing earlier can be affected any more.
- sorted, not sort
sorted returns a new list and leaves the caller’s alone. list.sort() reorders theirs in place, which the contract does not allow.
If the pairs were sorted by start, which other pair could the next one possibly overlap?
Sort by start. Walk through, keeping a result list. Each pair either overlaps the last one in the result, so you stretch that one’s end, or it does not, so you add it as a new one.
Check for start > end first. Then for start, end in sorted(...): if the result is not empty and start <= result[-1][1], set result[-1][1] to max(result[-1][1], end); otherwise append [start, end], a new list, not the caller’s.
def merge_intervals(intervals): if any(start > end for start, end in intervals): raise ValueError('a start comes after its end') merged = [] for start, end in sorted(intervals): if merged and start <= merged[-1][____]: merged[-1][1] = ____(merged[-1][1], end) else: merged.append([start, ____]) return merged
def merge_intervals(intervals):
if any(start > end for start, end in intervals):
raise ValueError("a start comes after its end")
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
Lists compare item by item, so sorting [start, end] pairs orders them by start, and by end where starts tie. No key is needed.
The loop unpacks each pair into two numbers and builds a new list from them. Appending the caller’s pair and then stretching its end would change their data.
Why sorting first turns an every-pair problem into one pass, that the sort is the most expensive step, and the two edge cases: touching ends and one range containing another.
If ranges arrive one at a time and you need the merged picture after each one, re-sorting everything every time gets slow; keep the merged list sorted and insert into it with bisect instead. And for dates, merging is only half the job: whether an end date is inclusive is a decision to make before the code, not in it.
- Return the gaps between the merged ranges instead: the free time in a calendar.
- Add one new interval to an already-merged, sorted list without sorting everything again.
- Make touching ends stay separate behind a flag, and decide what the default should be.