Lab: sorting problems

Problem 1 — Meeting rooms

Can a person attend all meetings in a schedule? Each meeting is an interval [start, end]. Two meetings conflict if one starts before the other has ended.

The key move: sort by start time. After sorting, any overlap must occur between adjacent intervals — you only need one pass to find it. Without sorting you would need to compare every pair: O(n²).

After sorting, why is checking only adjacent pairs enough? Because if meeting A ends after meeting C starts, and B is between them in sorted order, then B starts after A starts. If A overlaps C, A must also overlap B (or B overlaps C) — the overlap cannot "skip" a sorted neighbour. One linear scan is sufficient.

Problem 2 — Search insert position

Given a sorted list of distinct integers and a target, return the index where the target is found, or the index where it would be inserted to keep the list sorted. This is precisely what bisect_left computes.

The key move: bisect_left runs in O(log n) by binary search. A linear scan would be O(n) — fine for small lists, but the point is to recognise when a sorted structure enables a logarithmic lookup.

bisect_left finds the leftmost index where the list can accept target without violating sorted order. If target is already in the list, it returns its index. If not, it returns the position just before the first element that exceeds target. This is a direct application of the binary-search-on-value pattern from the previous lesson.

Problem 3 — Minimum ship capacity

A conveyor belt has packages with weights weights[0..n-1] (loaded in order). Find the minimum ship capacity that ships all packages in at most days days. Packages must be loaded in the given order — you cannot reorder them.

The key move: binary search on the answer. The search space is the capacity value: at minimum the ship must hold the heaviest single package (max(weights)), and at maximum it can hold all packages in one day (sum(weights)). For any candidate capacity c, you can test in O(n) whether it is sufficient by simulating greedy loading. The feasibility condition is monotone: if c works, c + 1 also works. Binary search finds the minimum valid c in O(n log(sum)).

The can_ship helper simulates greedy loading in O(n): keep adding packages to the current day until the next package would exceed the capacity, then start a new day. The outer binary search calls can_ship at most O(log(sum − max)) times, giving O(n log(sum)) total.

Done?

Three problems, one recurring theme: the naive approach iterates over all possibilities, but structure — sorted order, a sorted array's bisect points, a monotone feasibility condition — lets you discard half the search space at each step. Meeting rooms: sorting collapses an O(n²) comparison to O(n). Bisect insertion: the sorted precondition makes a single O(log n) call exact. Minimum capacity: framing the search space as a value range and the condition as a yes/no test unlocks O(n log n) over O(n × range) brute force.