Exercise: From given list of meetings of varying lengths, find the shortest number of meetings that can fit in the day

fewest-meetings.js

// Recursively create all combinations of the remaining items--at least those
// that are valid and aren't longer than those we've tested so far.
function buildCombinations(remaining, combo, process) {
  process.recordIteration();

  for (let i = 0; i < remaining.length; i++) {
    if (process.isDone()) {
      // global short-circuit
      return;
    }

    const pick = remaining[i];
    if (!combo.canAccept(pick)) {
      // the rest are not valid combinations
      continue;
    }

    const newCombo = combo.withItem(pick);
    if (newCombo.isFull() || remaining.length === 1) {
      // nothing more can be added
      process.consider(newCombo);
      continue;
    }

    const rest = [...remaining.slice(0, i), ...remaining.slice(i + 1)];
    buildCombinations(rest, newCombo, process);
  }
}

function meeting(hours) {
  return { hours, name: `meeting ${meeting.i++}` };
}
meeting.i = 0;

function optimize(meetings, hoursAvailable) {
  let shortestLength = meetings.length;
  let shortestCombo;
  let iterations = 0;

  const process = {
    consider(combo) {
      if (combo.items.length < shortestLength) {
        shortestCombo = combo;
        shortestLength = combo.items.length;
      }
    },
    isDone() {
      return shortestLength === 1;
    },
    recordIteration() {
      iterations++;
    }
  };

  class Combination {
    constructor(items = [], remainingHours) {
      this.items = items.slice();
      this.remainingHours = remainingHours;
    }
    canAccept(item) {
      return this.remainingHours >= item.hours;
    }
    isFull() {
      if (this.items.length >= shortestLength) {
        // if already as long as our shortest, don't bother adding more
        return true;
      }
      return this.remainingHours <= 0;
    }
    withItem(item) {
      return new Combination([...this.items, item], this.remainingHours - item.hours);
    }
  }

  const combo = new Combination([], hoursAvailable);
  buildCombinations(meetings, combo, process);

  console.log({ iterations });
  return shortestCombo.items;
}

console.log(optimize([
  meeting(26),
  meeting(1),
  meeting(11),
  meeting(9),
  meeting(2),
  meeting(3),
  meeting(1),
  meeting(4),
], 8));