Practice Problems

Most sorting problems are not "implement a sort" but "sort first, then the rest is easy". The four problems below practice sort-then-scan, multi-key ordering, custom comparators and reusing the merge step. Try each one before reading the solution.

Problem 1. Merge room bookings

Room bookings are given as (start, end) pairs of integers in no particular order. Merge bookings that overlap or touch, and return the periods when the room is actually in use, ordered by start time. For [(9, 11), (13, 15), (10, 12), (15, 16)] the answer is [[9, 12], [13, 16]].

Approach: after sorting by start time, a booking can only overlap the last merged period. Scan in order; if the current start is at most the last end, extend that end, otherwise open a new period. Sorting costs O(n log n) and the scan O(n).

def merge_bookings(bookings):
    result = []
    for start, end in sorted(bookings):
        if result and start <= result[-1][1]:
            result[-1][1] = max(result[-1][1], end)
        else:
            result.append([start, end])
    return result

print(merge_bookings([(9, 11), (13, 15), (10, 12), (15, 16)]))  # [[9, 12], [13, 16]]

Problem 2. Contest leaderboard

Each contestant has (name, score, seconds). Rank by score descending, then by time ascending, then by name alphabetically.

Approach: one tuple key expresses all three criteria, and negating the numeric score turns it into descending order. If a criterion that cannot be negated (such as a string) must be descending, run several stable sorts from the least to the most significant criterion. Python's reverse=True preserves stability too.

players = [("lee", 90, 300), ("kim", 95, 410), ("park", 90, 280), ("choi", 90, 300)]

ranked = sorted(players, key=lambda p: (-p[1], p[2], p[0]))
print([p[0] for p in ranked])  # ['kim', 'park', 'choi', 'lee']

# The same result with repeated stable sorts, least significant key first
step = sorted(players, key=lambda p: p[0])
step = sorted(step, key=lambda p: p[2])
step = sorted(step, key=lambda p: p[1], reverse=True)
print([p[0] for p in step])    # ['kim', 'park', 'choi', 'lee']

Problem 3. Largest concatenated number

Given non-negative integers, arrange them so that their concatenation is the largest possible number, and return it as a string. For [3, 30, 34, 5, 9] the answer is "9534330". If all values are zero, return "0".

Approach: sorting numerically or lexicographically fails on pairs like 3 and 30. Instead compare two strings a and b by whichever of a + b and b + a is larger. This comparison is transitive, so it is a valid sort order. Strip leading zeros so that becomes .