Patterns

Sort first; iterate making the locally optimal choice each step

When to useInterval scheduling, merge cost minimization, partition labels

iterative

University Career Fair

twitter_oa_university_career_fair

Choose A Flask

amazon_oa_choose_a_flask

Earliest Time To Complete Deliveries | Schedule Deliveries

earliest_time_to_complete_deliveries

Unique Twitter User ID Set

twitter_oa_unique_user_id_set

INITIALIZE

sort by relevant criterion; init accumulator

const intervals = starts.map((s, i) => [s, s + durations[i]]);
intervals.sort((a, b) => a[1] - b[1]);
let count = 0;
let lastEnd = -Infinity;

const sortedReq = [...requirements].sort((a, b) => a - b);
const flaskMarkings = new Map();
for (const [id, value] of markings) {
  if (!flaskMarkings.has(id)) flaskMarkings.set(id, []);
  flaskMarkings.get(id).push(value);
}
let bestLoss = Infinity;
let bestFlask = -1;

const sortedOpens = [...openTimes].sort((a, b) => a - b);
const sortedCosts = [...deliveryCosts].sort((a, b) => a - b);
let latest = 0;

const sorted = [...boxTypes].sort((a, b) => b[1] - a[1]);
let total = 0;
let remaining = truckSize;

const sorted = [...activities].sort((a, b) => a[1] - b[1]);
let count = 0;
let lastEnd = -Infinity;

l.sort((a, b) => a - b);
let total = l[0];
let prev = l[0];

TRAVERSE

for each item in sorted order

for (const [start, end] of intervals) {

for (const [id, flaskMarks] of flaskMarkings) {

for (const open of sortedOpens) {

for (const [boxes, units] of sorted) {

for (const [start, end] of sorted) {

for (let i = 1; i < l.length; i++) {

[CHOOSE]

greedy decision; update accumulator

  if (start >= lastEnd) {
    count++;
    lastEnd = end;
  }

  let loss = 0; let i = 0; let valid = true;
  for (const req of sortedReq) {
    while (i < flaskMarks.length && flaskMarks[i] < req) i++;
    if (i === flaskMarks.length) { valid = false; break; }
    loss += flaskMarks[i] - req;
  }
  if (valid && loss < bestLoss) { bestLoss = loss; bestFlask = id; }

  for (let i = 0; i < 4; i++) {
    const cost = sortedCosts.pop();
    const finish = open + cost;
    if (finish > latest) latest = finish;
  }

  const take = Math.min(boxes, remaining);
  total += take * units;
  remaining -= take;
  if (remaining === 0) break;

  if (start >= lastEnd) {
    count += 1;
    lastEnd = end;
  }

  const curr = Math.max(l[i], prev + 1);
  total += curr;
  prev = curr;

RETURN

return accumulator

return count;

return bestFlask;

return latest;

return total;

return count;

return total;