Greedy & interval patterns

A greedy algorithm makes the locally best choice at each step and never revisits it. Greedy is only correct when you can argue the local pick is safe — usually an exchange argument: any optimal solution can be rewritten to include your choice without getting worse. Say that argument out loud; 'greedy because it feels right' is how candidates fail these.

• Interval scheduling: to attend the most non-overlapping meetings, sort by end time and always take the earliest-ending compatible one — it leaves the most room for everything after it.
• Jump game: one pass tracking the furthest reachable index; if your position ever exceeds it, you are stuck — O(n).
• Kadane's (maximum subarray): at each element, either extend the running sum or restart at the element (cur = max(x, cur + x)), tracking the best — O(n), handles all-negative arrays.

Merge overlapping intervals

The interval workhorse: sort by start, then sweep once, either extending the last merged interval or appending a new one. Sorting dominates the cost: O(n log n).

def merge(intervals):
    intervals.sort(key=lambda iv: iv[0])
    out = []
    for start, end in intervals:
        if out and start <= out[-1][1]:
            out[-1][1] = max(out[-1][1], end)   # overlap -> extend
        else:
            out.append([start, end])            # gap -> start fresh
    return out