贪心与调度

def min_jumps(nums: list[int]) -> int:
    """Fewest jumps from index 0 to the last; nums[i] is the longest jump from i (LC 45)."""
    jumps = end = far = 0  # indexes up to end take `jumps` jumps; far: the next jump's reach
    for i in range(len(nums) - 1):
        far = max(far, i + nums[i])
        if i == end:  # this jump's range is used up: take another
            jumps += 1
            end = far
    return jumps

// Fewest jumps from index 0 to the last; nums[i] is the longest jump from i (LC 45).
int minJumps(const vector<int>& nums) {
    int jumps = 0, end = 0, far = 0;  // indexes up to end take `jumps` jumps; far: the next jump's reach
    for (int i = 0; i + 1 < (int)nums.size(); i++) {
        far = max(far, i + nums[i]);
        if (i == end) {  // this jump's range is used up: take another
            jumps++;
            end = far;
        }
    }
    return jumps;
}

class Solution {
    // Fewest jumps from index 0 to the last; nums[i] is the longest jump from i (LC 45).
    int minJumps(int[] nums) {
        int jumps = 0, end = 0, far = 0; // indexes up to end take `jumps` jumps; far: the next jump's reach
        for (int i = 0; i + 1 < nums.length; i++) {
            far = Math.max(far, i + nums[i]);
            if (i == end) { // this jump's range is used up: take another
                jumps++;
                end = far;
            }
        }
        return jumps;
    }
}

// minJumps returns the fewest jumps from index 0 to the last; nums[i] is the longest jump from i.
func minJumps(nums []int) int {
	jumps, end, far := 0, 0, 0 // indexes up to end take `jumps` jumps; far: the next jump's reach
	for i := 0; i+1 < len(nums); i++ {
		far = max(far, i+nums[i])
		if i == end { // this jump's range is used up: take another
			jumps++
			end = far
		}
	}
	return jumps
}

import heapq


def schedule_course(courses: list[list[int]]) -> int:
    """Most courses [duration, last day] you can finish one at a time (LC 630)."""
    taken: list[int] = []  # chosen durations as a max-heap (negated)
    day = 0
    for duration, last in sorted(courses, key=lambda c: c[1]):  # earliest deadline first
        heapq.heappush(taken, -duration)
        day += duration
        if day > last:  # past the deadline: drop the longest course taken so far
            day += heapq.heappop(taken)
    return len(taken)

// Most courses {duration, last day} you can finish one at a time (LC 630).
int scheduleCourse(vector<pair<int, int>> courses) {
    sort(courses.begin(), courses.end(), [](auto& a, auto& b) { return a.second < b.second; });  // earliest deadline first
    priority_queue<int> taken;  // chosen durations, longest on top
    long long day = 0;
    for (auto [duration, last] : courses) {
        taken.push(duration);
        day += duration;
        if (day > last) {  // past the deadline: drop the longest course taken so far
            day -= taken.top();
            taken.pop();
        }
    }
    return taken.size();
}

class Solution {
    // Most courses {duration, last day} you can finish one at a time (LC 630).
    int scheduleCourse(int[][] courses) {
        int[][] sorted = courses.clone();
        Arrays.sort(sorted, Comparator.comparingInt(c -> c[1])); // earliest deadline first
        PriorityQueue<Integer> taken = new PriorityQueue<>(Comparator.reverseOrder()); // longest on top
        long day = 0;
        for (int[] c : sorted) {
            taken.offer(c[0]);
            day += c[0];
            if (day > c[1]) day -= taken.poll(); // past the deadline: drop the longest course taken so far
        }
        return taken.size();
    }
}

import (
	"container/heap"
	"sort"
)

// maxHeap is a max-heap of ints for container/heap.
type maxHeap []int

func (h maxHeap) Len() int           { return len(h) }
func (h maxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h maxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *maxHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *maxHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

// scheduleCourse returns the most courses {duration, last day} you can finish one at a time (LC 630).
func scheduleCourse(courses [][2]int) int {
	sorted := append([][2]int(nil), courses...)
	sort.Slice(sorted, func(i, j int) bool { return sorted[i][1] < sorted[j][1] }) // earliest deadline first
	taken := &maxHeap{} // chosen durations, longest on top
	day := 0
	for _, c := range sorted {
		heap.Push(taken, c[0])
		day += c[0]
		if day > c[1] { // past the deadline: drop the longest course taken so far
			day -= heap.Pop(taken).(int)
		}
	}
	return taken.Len()
}