621. Task Scheduler☆

function leastInterval(tasks: string[], n: number): number {
  // Count task frequencies
  const freq = new Map<string, number>();
  for (const t of tasks) freq.set(t, (freq.get(t) ?? 0) + 1);

  // Find maximum frequency and how many tasks share it
  let maxCount = 0;
  for (const v of freq.values()) maxCount = Math.max(maxCount, v);
  let numMax = 0;
  for (const v of freq.values()) if (v === maxCount) numMax++;

  // Greedy formula: (maxCount - 1) gaps of size (n + 1), plus tasks that share max
  const formula = (maxCount - 1) * (n + 1) + numMax;

  // If tasks are dense enough they fill every idle slot, no idle needed
  return Math.max(formula, tasks.length);
}

function findKthLargest(nums: number[], k: number): number {
  // Min-heap of size k — the root is always the kth largest seen so far.
  const heap: number[] = [];

  function push(val: number): void {
    heap.push(val);
    let i = heap.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (heap[p] > heap[i]) { [heap[p], heap[i]] = [heap[i], heap[p]]; i = p; }
      else break;
    }
  }

  function pop(): number {
    const top = heap[0];
    const last = heap.pop()!;
    if (heap.length > 0) {
      heap[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let s = i;
        if (l < heap.length && heap[l] < heap[s]) s = l;
        if (r < heap.length && heap[r] < heap[s]) s = r;
        if (s === i) break;
        [heap[i], heap[s]] = [heap[s], heap[i]]; i = s;
      }
    }
    return top;
  }

  for (const n of nums) {
    push(n);                          // add every element
    if (heap.length > k) pop();       // evict the minimum when over-full
  }
  return heap[0];                     // root = kth largest
}

function lastStoneWeight(stones: number[]): number {
  // Max-heap (simulated with a max-first comparator via a custom MinHeap inverted).
  // Here we implement a simple binary max-heap inline for clarity.
  const heap: number[] = [];

  function push(val: number): void {
    heap.push(val);
    let i = heap.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (heap[p] >= heap[i]) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  }

  function pop(): number {
    const top = heap[0];
    const last = heap.pop()!;
    if (heap.length > 0) {
      heap[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let max = i;
        if (l < heap.length && heap[l] > heap[max]) max = l;
        if (r < heap.length && heap[r] > heap[max]) max = r;
        if (max === i) break;
        [heap[i], heap[max]] = [heap[max], heap[i]];
        i = max;
      }
    }
    return top;
  }

  for (const s of stones) push(s);

  while (heap.length > 1) {
    const y = pop(); // heaviest
    const x = pop(); // second heaviest
    if (y !== x) push(y - x); // leftover fragment
  }

  return heap.length === 0 ? 0 : heap[0];
}

function findMaximizedCapital(
  k: number,
  w: number,
  profits: number[],
  capital: number[],
): number {
  const n = profits.length;

  // Pair each project as [capital, profit], sorted by capital ascending.
  const projects = Array.from({ length: n }, (_, i) => [capital[i], profits[i]]);
  projects.sort((a, b) => a[0] - b[0]);

  // Max-heap of the profits of every project we can currently afford.
  const affordable = new MaxHeap();
  let i = 0;

  for (let round = 0; round < k; round++) {
    // Unlock every project whose capital requirement is within reach.
    while (i < n && projects[i][0] <= w) {
      affordable.push(projects[i][1]);
      i++;
    }
    // Nothing affordable now → nothing ever will be. Stop early.
    if (affordable.size === 0) break;
    // Greedily bank the most profitable affordable project.
    w += affordable.pop();
  }

  return w;
}