Greedy and Intervals

def merge_intervals(intervals):
    """Sort by START. O(n log n)."""
    if not intervals:
        return []
    intervals.sort(key=lambda x: x[0])
    out = [list(intervals[0])]
    for start, end in intervals[1:]:
        if start <= out[-1][1]:             # overlap or touch
            out[-1][1] = max(out[-1][1], end)
        else:
            out.append([start, end])
    return out

def insert_interval(intervals, new):
    """intervals is already sorted and disjoint. O(n), no sort needed."""
    out, i, n = [], 0, len(intervals)
    while i < n and intervals[i][1] < new[0]:
        out.append(intervals[i])            # entirely before
        i += 1
    start, end = new
    while i < n and intervals[i][0] <= end:
        start = min(start, intervals[i][0])  # absorb every overlap
        end = max(end, intervals[i][1])
        i += 1
    out.append([start, end])
    out.extend(intervals[i:])
    return out

def max_non_overlapping(intervals):
    """Sort by END. The classic activity-selection greedy."""
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[1])
    count, last_end = 0, float("-inf")
    for start, end in intervals:
        if start >= last_end:               # no conflict, take it
            count += 1
            last_end = end
    return count

def erase_overlap_intervals(intervals):
    """Minimum removals = total - maximum kept."""
    return len(intervals) - max_non_overlapping(intervals)

def find_min_arrows(points):
    """Minimum arrows to burst every balloon. Sort by END, shoot at it."""
    if not points:
        return 0
    points.sort(key=lambda x: x[1])
    arrows, last = 1, points[0][1]
    for start, end in points[1:]:
        if start > last:                    # touching counts as a hit
            arrows += 1
            last = end
    return arrows

import heapq

def min_meeting_rooms(intervals):
    """Heap of end times. Sort by START. O(n log n)."""
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[0])
    ends = []
    for start, end in intervals:
        if ends and ends[0] <= start:
            heapq.heapreplace(ends, end)    # reuse the earliest-freed room
        else:
            heapq.heappush(ends, end)
    return len(ends)

def min_meeting_rooms_sweep(intervals):
    """Sweep line. Sort starts and ends separately, walk both. O(n log n)."""
    starts = sorted(s for s, _ in intervals)
    ends = sorted(e for _, e in intervals)
    rooms = best = 0
    i = j = 0
    while i < len(starts):
        if starts[i] < ends[j]:
            rooms += 1
            best = max(best, rooms)
            i += 1
        else:
            rooms -= 1
            j += 1
    return best

def car_pooling(trips, capacity):
    """Difference array on a bounded timeline. O(n + T)."""
    diff = [0] * 1001
    for num, start, end in trips:
        diff[start] += num
        diff[end] -= num
    onboard = 0
    for d in diff:
        onboard += d
        if onboard > capacity:
            return False
    return True

def interval_intersection(a, b):
    """Both sorted and disjoint. Two pointers, O(n + m)."""
    out, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        lo = max(a[i][0], b[j][0])
        hi = min(a[i][1], b[j][1])
        if lo <= hi:
            out.append([lo, hi])
        if a[i][1] < b[j][1]:               # advance the one ending first
            i += 1
        else:
            j += 1
    return out

def employee_free_time(schedules):
    """Gaps common to everyone. Merge all intervals, report the holes."""
    flat = sorted((s, e) for person in schedules for s, e in person)
    out, end = [], flat[0][1]
    for s, e in flat[1:]:
        if s > end:
            out.append([end, s])
        end = max(end, e)
    return out

// Java: sort intervals with a comparator, never with subtraction
Arrays.sort(intervals, (x, y) -> Integer.compare(x[1], y[1]));   // by end
PriorityQueue<Integer> ends = new PriorityQueue<>();
for (int[] iv : intervals) {
    if (!ends.isEmpty() && ends.peek() <= iv[0]) ends.poll();
    ends.offer(iv[1]);
}
int rooms = ends.size();

def can_jump(nums):
    """Jump Game. Track the furthest reachable index. O(n), O(1)."""
    reach = 0
    for i, x in enumerate(nums):
        if i > reach:
            return False                    # a gap we cannot cross
        reach = max(reach, i + x)
    return True

def min_jumps(nums):
    """Jump Game II. Implicit BFS over levels, O(n)."""
    jumps = cur_end = furthest = 0
    for i in range(len(nums) - 1):
        furthest = max(furthest, i + nums[i])
        if i == cur_end:                    # exhausted this level
            jumps += 1
            cur_end = furthest
    return jumps

def can_complete_circuit(gas, cost):
    """Gas Station. If the total is non-negative a start exists, and the
    index just after the lowest running deficit is it. O(n)."""
    if sum(gas) < sum(cost):
        return -1
    start = tank = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start = i + 1                   # everything before i fails too
            tank = 0
    return start

def partition_labels(s):
    """Partition so each letter appears in one part only. O(n)."""
    last = {ch: i for i, ch in enumerate(s)}
    out, start, end = [], 0, 0
    for i, ch in enumerate(s):
        end = max(end, last[ch])
        if i == end:                        # nothing later reaches back
            out.append(end - start + 1)
            start = i + 1
    return out

def task_scheduler(tasks, n):
    """Minimum time with a cooldown of n between identical tasks.
    The most frequent task sets the skeleton. O(len(tasks))."""
    from collections import Counter
    counts = Counter(tasks)
    top = max(counts.values())
    ties = sum(1 for v in counts.values() if v == top)
    return max(len(tasks), (top - 1) * (n + 1) + ties)

def fractional_knapsack(weights, values, capacity):
    """Items divisible, so greedy by value density is optimal.
    The 0/1 version is NOT, that one needs DP."""
    items = sorted(zip(weights, values), key=lambda wv: -wv[1] / wv[0])
    total = 0.0
    for w, v in items:
        if capacity >= w:
            total += v
            capacity -= w
        else:
            total += v * capacity / w       # take a fraction, then stop
            break
    return total

def largest_number(nums):
    """Concatenate for the largest value. Custom pairwise comparator."""
    from functools import cmp_to_key
    def cmp(x, y):
        if x + y > y + x:
            return -1
        if x + y < y + x:
            return 1
        return 0
    out = "".join(sorted(map(str, nums), key=cmp_to_key(cmp)))
    return "0" if out[0] == "0" else out

def two_city_scheduling(costs):
    """Send n to each city. Sort by the cost DIFFERENCE, not by cost."""
    costs.sort(key=lambda c: c[0] - c[1])
    n = len(costs) // 2
    return (sum(c[0] for c in costs[:n])
            + sum(c[1] for c in costs[n:]))