12. Sorting & Advanced Search

What Interviewers Test Here

• Python's sorted() and custom key functions
• Merge sort for inversion counting
• Binary search on the answer space (not just sorted arrays)

import bisect

# --- Custom sort ---
intervals = [[1,4],[3,6],[0,2]]
intervals.sort(key=lambda x: x[0])   # sort by start time

# --- Merge intervals ---
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

# --- Binary search on answer ---
def min_days_bouquets(bloom_day: list[int], m: int, k: int) -> int:
    def can_make(day: int) -> bool:
        bouquets = flowers = 0
        for d in bloom_day:
            if d <= day:
                flowers += 1
                if flowers == k:
                    bouquets += 1; flowers = 0
            else:
                flowers = 0
        return bouquets >= m

    if len(bloom_day) < m * k: return -1
    l, r = min(bloom_day), max(bloom_day)
    while l < r:
        mid = (l + r) // 2
        if can_make(mid): r = mid
        else:             l = mid + 1
    return l

---

Conceptual Q&A

Q1: "Given a list of intervals, merge all overlapping ones."

Walkthrough:

"Two intervals [a,b] and [c,d] overlap if c <= b (assuming a <= c after sorting). If I sort intervals by start time, I only ever need to compare a new interval with the last merged interval.

Algorithm: sort by start, then iterate. If the new interval's start ≤ last merged end → merge (update end to max). Otherwise → add as new interval. $O(n \log n)$ due to sort."

(See implementation above)

---