Minimum Number of Refueling Stops

class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        priority_queue<int> pq;
        int stops = 0, fuel = startFuel, i = 0;
        const int n = stations.size();
        while (fuel < target) {
            while (i < n && stations[i][0] <= fuel) pq.push(stations[i++][1]);
            if (pq.empty()) return -1;
            fuel += pq.top(); pq.pop();
            ++stops;
        }
        return stops;
    }
};

type intMaxHeap []int

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

func minRefuelStops(target int, startFuel int, stations [][]int) int {
    pq := &intMaxHeap{}
    stops, fuel, i := 0, startFuel, 0
    n := len(stations)
    for fuel < target {
        for i < n && stations[i][0] <= fuel {
            heap.Push(pq, stations[i][1])
            i++
        }
        if pq.Len() == 0 {
            return -1
        }
        fuel += heap.Pop(pq).(int)
        stops++
    }
    return stops
}

import heapq
from typing import List

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        pq: List[int] = []  # max-heap via negation
        stops = 0
        fuel = startFuel
        i = 0
        n = len(stations)
        while fuel < target:
            while i < n and stations[i][0] <= fuel:
                heapq.heappush(pq, -stations[i][1])
                i += 1
            if not pq:
                return -1
            fuel += -heapq.heappop(pq)
            stops += 1
        return stops

class MaxHeap {
    constructor() { this.h = []; }
    size() { return this.h.length; }
    push(v) { this.h.push(v); this.up(this.h.length - 1); }
    pop() {
        const top = this.h[0];
        const last = this.h.pop();
        if (this.h.length) { this.h[0] = last; this.down(0); }
        return top;
    }
    up(i) {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p] >= this.h[i]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    down(i) {
        const n = this.h.length;
        while (true) {
            const l = 2 * i + 1, r = l + 1;
            let s = i;
            if (l < n && this.h[l] > this.h[s]) s = l;
            if (r < n && this.h[r] > this.h[s]) s = r;
            if (s === i) break;
            [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
            i = s;
        }
    }
}

function minRefuelStops(target, startFuel, stations) {
    const pq = new MaxHeap();
    let stops = 0, fuel = startFuel, i = 0;
    const n = stations.length;
    while (fuel < target) {
        while (i < n && stations[i][0] <= fuel) pq.push(stations[i++][1]);
        if (pq.size() === 0) return -1;
        fuel += pq.pop();
        stops++;
    }
    return stops;
}

class Solution {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        int stops = 0, fuel = startFuel, i = 0;
        int n = stations.length;
        while (fuel < target) {
            while (i < n && stations[i][0] <= fuel) pq.offer(stations[i++][1]);
            if (pq.isEmpty()) return -1;
            fuel += pq.poll();
            stops++;
        }
        return stops;
    }
}

class MaxHeap {
    private h: number[] = [];
    size(): number { return this.h.length; }
    push(v: number): void { this.h.push(v); this.up(this.h.length - 1); }
    pop(): number {
        const top = this.h[0];
        const last = this.h.pop()!;
        if (this.h.length) { this.h[0] = last; this.down(0); }
        return top;
    }
    private up(i: number): void {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p] >= this.h[i]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    private down(i: number): void {
        const n = this.h.length;
        while (true) {
            const l = 2 * i + 1, r = l + 1;
            let s = i;
            if (l < n && this.h[l] > this.h[s]) s = l;
            if (r < n && this.h[r] > this.h[s]) s = r;
            if (s === i) break;
            [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
            i = s;
        }
    }
}

function minRefuelStops(target: number, startFuel: number, stations: number[][]): number {
    const pq = new MaxHeap();
    let stops = 0, fuel = startFuel, i = 0;
    const n = stations.length;
    while (fuel < target) {
        while (i < n && stations[i][0] <= fuel) pq.push(stations[i++][1]);
        if (pq.size() === 0) return -1;
        fuel += pq.pop();
        stops++;
    }
    return stops;
}