Priority scheduling

1record Event(int time, int type, int id) {}      // type 0 = arrival, 1 = departure
2static int[] simulate(int[] arrival, int[] service) {            // single server, first come first served
3    PriorityQueue<Event> events = new PriorityQueue<>(Comparator.comparingInt(Event::time).thenComparingInt(Event::type).thenComparingInt(Event::id));
4    for (int i = 0; i < arrival.length; i++) events.add(new Event(arrival[i], 0, i));
5    int[] departure = new int[arrival.length];
6    Deque<Integer> waiting = new ArrayDeque<>();
7    boolean busy = false;
8    while (!events.isEmpty()) {
9        Event e = events.poll();                 // the earliest event: advance the clock to it
10        if (e.type() == 0) {
11            if (busy) waiting.add(e.id());
12            else { busy = true; events.add(new Event(e.time() + service[e.id()], 1, e.id())); }
13        } else {
14            departure[e.id()] = e.time();
15            if (waiting.isEmpty()) busy = false;
16            else { int next = waiting.poll(); events.add(new Event(e.time() + service[next], 1, next)); }
17        }
18    }
19    return departure;
20}

1record Task(String name, int arrival, int burst, int priority) {}
2static double schedule(List<Task> tasks) {       // highest priority first; ties go to the earlier arrival
3    tasks.sort(Comparator.comparingInt(Task::arrival));
4    PriorityQueue<Task> ready = new PriorityQueue<>(
5        Comparator.comparingInt(Task::priority).reversed().thenComparingInt(Task::arrival));
6    int time = 0, next = 0, totalWait = 0;
7    while (next < tasks.size() || !ready.isEmpty()) {
8        while (next < tasks.size() && tasks.get(next).arrival() <= time) ready.add(tasks.get(next++));   // arrivals
9        if (ready.isEmpty()) { time = tasks.get(next).arrival(); continue; }                             // idle gap
10        Task run = ready.poll();                 // the best waiting task
11        totalWait += time - run.arrival();
12        time += run.burst();                     // non-preemptive: it runs to completion
13    }
14    return (double) totalWait / tasks.size();
15}

1// adj.get(u) holds {v, weight}, all weights >= 0
2static long[] dijkstra(List<List<int[]>> adj, int source) {
3    long[] dist = new long[adj.size()];
4    Arrays.fill(dist, Long.MAX_VALUE);
5    dist[source] = 0;
6    PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(e -> e[1]));   // {vertex, distance}
7    pq.add(new long[]{source, 0});
8    while (!pq.isEmpty()) {
9        long[] cur = pq.poll();
10        int u = (int) cur[0];
11        if (cur[1] > dist[u]) continue;          // a stale entry: a shorter path was found after this was pushed
12        for (int[] edge : adj.get(u)) {
13            long nd = cur[1] + edge[1];
14            if (nd < dist[edge[0]]) { dist[edge[0]] = nd; pq.add(new long[]{edge[0], nd}); }
15        }
16    }
17    return dist;
18}

1// grid: '#' is a wall; returns the number of steps from (sr, sc) to (tr, tc), or -1
2static int aStar(char[][] g, int sr, int sc, int tr, int tc) {
3    int R = g.length, C = g[0].length;
4    int[][] best = new int[R][C];
5    for (int[] row : best) Arrays.fill(row, Integer.MAX_VALUE);
6    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e[0]));    // {g + h, g, r, c}
7    best[sr][sc] = 0;
8    pq.add(new int[]{Math.abs(sr - tr) + Math.abs(sc - tc), 0, sr, sc});
9    int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1};
10    while (!pq.isEmpty()) {
11        int[] cur = pq.poll();
12        int gCost = cur[1], r = cur[2], c = cur[3];
13        if (r == tr && c == tc) return gCost;
14        if (gCost > best[r][c]) continue;        // a stale entry
15        for (int d = 0; d < 4; d++) {
16            int nr = r + dr[d], nc = c + dc[d];
17            if (nr < 0 || nc < 0 || nr >= R || nc >= C || g[nr][nc] == '#') continue;
18            if (gCost + 1 < best[nr][nc]) {
19                best[nr][nc] = gCost + 1;
20                pq.add(new int[]{gCost + 1 + Math.abs(nr - tr) + Math.abs(nc - tc), gCost + 1, nr, nc});
21            }
22        }
23    }
24    return -1;
25}

1static long huffmanCost(int[] freq) {            // the total encoded length in bits
2    PriorityQueue<Long> heap = new PriorityQueue<>();
3    for (int f : freq) heap.add((long) f);
4    long total = 0;
5    while (heap.size() > 1) {
6        long merged = heap.poll() + heap.poll();  // the two lightest trees
7        total += merged;                         // every merge adds one bit to every symbol below it
8        heap.add(merged);
9    }
10    return total;
11}