Greedy

function maxActivities(activities) { // [start, end]
  activities.sort((a, b) => a[1] - b[1]);
  let count = 0, lastEnd = -Infinity;
  for (const [s, e] of activities) {
    if (s >= lastEnd) { count++; lastEnd = e; }
  }
  return count;
}

function jobSequencing(jobs) { // {id, deadline, profit}
  jobs.sort((a, b) => b.profit - a.profit);
  const maxD = Math.max(...jobs.map((j) => j.deadline));
  const slot = new Array(maxD + 1).fill(null);
  let profit = 0, count = 0;
  for (const j of jobs) {
    for (let d = j.deadline; d >= 1; d--) {
      if (!slot[d]) { slot[d] = j.id; profit += j.profit; count++; break; }
    }
  }
  return { count, profit };
}

function huffman(freq) { // freq: { char: count }
  let heap = Object.entries(freq).map(([ch, f]) => ({ ch, f, left: null, right: null }));
  heap.sort((a, b) => a.f - b.f);
  while (heap.length > 1) {
    const a = heap.shift(), b = heap.shift();
    const node = { ch: null, f: a.f + b.f, left: a, right: b };
    let i = heap.findIndex((x) => x.f > node.f);
    i === -1 ? heap.push(node) : heap.splice(i, 0, node);
  }
  const codes = {};
  const walk = (n, code) => {
    if (!n) return;
    if (n.ch !== null) { codes[n.ch] = code || '0'; return; }
    walk(n.left, code + '0');
    walk(n.right, code + '1');
  };
  walk(heap[0], '');
  return codes;
}

function fractionalKnapsack(items, capacity) { // items: [value, weight]
  items.sort((a, b) => b[0] / b[1] - a[0] / a[1]);
  let total = 0;
  for (const [v, w] of items) {
    if (capacity >= w) { capacity -= w; total += v; }
    else { total += v * (capacity / w); break; }
  }
  return total;
}

function minCoins(amount, coins = [1, 2, 5, 10, 20, 50, 100, 500, 2000]) {
  coins.sort((a, b) => b - a);
  const used = [];
  for (const c of coins) while (amount >= c) { amount -= c; used.push(c); }
  return used;
}

function minPlatforms(arr, dep) {
  arr.sort((a, b) => a - b);
  dep.sort((a, b) => a - b);
  let platforms = 0, best = 0, i = 0, j = 0;
  while (i < arr.length) {
    if (arr[i] <= dep[j]) { platforms++; i++; best = Math.max(best, platforms); }
    else { platforms--; j++; }
  }
  return best;
}

function maxSumAfterKNegations(a, k) {
  a.sort((x, y) => x - y);
  for (let i = 0; i < a.length && k > 0 && a[i] < 0; i++) { a[i] = -a[i]; k--; }
  if (k % 2 === 1) { const m = Math.min(...a); const idx = a.indexOf(m); a[idx] = -a[idx]; }
  return a.reduce((s, v) => s + v, 0);
}

function maxSumIndexProduct(a) {
  a.sort((x, y) => x - y);
  return a.reduce((s, v, i) => s + v * i, 0);
}

function smallestNumber(digits, sum) {
  if (sum === 0) return digits === 1 ? '0' : '-1';
  if (sum > 9 * digits) return '-1';
  const res = new Array(digits).fill(0);
  sum -= 1; // reserve for the leading digit
  for (let i = digits - 1; i > 0; i--) {
    if (sum > 9) { res[i] = 9; sum -= 9; } else { res[i] = sum; sum = 0; }
  }
  res[0] = sum + 1;
  return res.join('');
}

function minCutCost(horizontal, vertical) {
  horizontal.sort((a, b) => b - a);
  vertical.sort((a, b) => b - a);
  let hi = 0, vi = 0, hPieces = 1, vPieces = 1, cost = 0;
  while (hi < horizontal.length && vi < vertical.length) {
    if (horizontal[hi] >= vertical[vi]) { cost += horizontal[hi++] * vPieces; hPieces++; }
    else { cost += vertical[vi++] * hPieces; vPieces++; }
  }
  while (hi < horizontal.length) cost += horizontal[hi++] * vPieces;
  while (vi < vertical.length) cost += vertical[vi++] * hPieces;
  return cost;
}

function waterConnection(n, pipes) { // pipes: [from, to, diameter]
  const out = new Map(), incoming = new Set();
  for (const [a, b, d] of pipes) { out.set(a, [b, d]); incoming.add(b); }
  const res = [];
  for (const [a] of out) {
    if (incoming.has(a)) continue;
    let cur = a, minD = Infinity;
    while (out.has(cur)) { const [nxt, d] = out.get(cur); minD = Math.min(minD, d); cur = nxt; }
    res.push([a, cur, minD]); // [tank house, tap house, max deliverable diameter]
  }
  return res;
}

// Wine trading in Gergovia — total transport cost
function gergovia(demands) { // + = wants to buy, - = wants to sell
  let carry = 0n, cost = 0n;
  for (const d of demands) {
    carry += BigInt(d);
    cost += carry < 0n ? -carry : carry;
  }
  return cost.toString();
}

// Smallest subset whose sum exceeds the rest
function smallestSubsetOverHalf(a) {
  a.sort((x, y) => y - x);
  const total = a.reduce((s, v) => s + v, 0);
  let acc = 0, k = 0;
  for (const v of a) { acc += v; k++; if (acc > total - acc) break; }
  return k;
}

function canJump(nums) {
  let reach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > reach) return false;
    reach = Math.max(reach, i + nums[i]);
  }
  return true;
}

function partitionLabels(s) {
  const last = {};
  for (let i = 0; i < s.length; i++) last[s[i]] = i;
  const res = [];
  let start = 0, end = 0;
  for (let i = 0; i < s.length; i++) {
    end = Math.max(end, last[s[i]]);
    if (i === end) { res.push(end - start + 1); start = i + 1; }
  }
  return res;
}

function isNStraightHand(hand, size) {
  if (hand.length % size) return false;
  const cnt = new Map();
  for (const x of hand) cnt.set(x, (cnt.get(x) ?? 0) + 1);
  for (const x of [...cnt.keys()].sort((a, b) => a - b)) {
    const need = cnt.get(x);
    if (!need) continue;
    for (let v = x; v < x + size; v++) {
      if ((cnt.get(v) ?? 0) < need) return false;
      cnt.set(v, cnt.get(v) - need);
    }
  }
  return true;
}

function candy(ratings) {
  const n = ratings.length, c = new Array(n).fill(1);
  for (let i = 1; i < n; i++) if (ratings[i] > ratings[i - 1]) c[i] = c[i - 1] + 1;
  for (let i = n - 2; i >= 0; i--) if (ratings[i] > ratings[i + 1]) c[i] = Math.max(c[i], c[i + 1] + 1);
  return c.reduce((a, b) => a + b, 0);
}

function eraseOverlapIntervals(intervals) {
  intervals.sort((a, b) => a[1] - b[1]);
  let kept = 0, end = -Infinity;
  for (const [s, e] of intervals) {
    if (s >= end) { kept++; end = e; }
  }
  return intervals.length - kept;
}

function findMinArrowShots(points) {
  points.sort((a, b) => a[1] - b[1]);
  let arrows = 0, pos = -Infinity;
  for (const [s, e] of points) {
    if (s > pos) { arrows++; pos = e; }
  }
  return arrows;
}