// Activity Selection — O(n log n) for sort, O(n) after
function activitySelection(activities) {
  // Sort by end time (greedy choice: earliest end first)
  activities.sort((a, b) => a.end - b.end);

  const selected = [activities[0]];
  let lastEnd = activities[0].end;

  for (let i = 1; i < activities.length; i++) {
    // An activity is compatible if it starts after the last one ends
    if (activities[i].start >= lastEnd) {
      selected.push(activities[i]);
      lastEnd = activities[i].end;
    }
  }

  return selected;
}

const activities = [
  { name: 'A', start: 1, end: 4 },
  { name: 'B', start: 3, end: 5 },
  { name: 'C', start: 0, end: 6 },
  { name: 'D', start: 5, end: 7 },
  { name: 'E', start: 3, end: 9 },
  { name: 'F', start: 5, end: 9 },
  { name: 'G', start: 6, end: 10 },
  { name: 'H', start: 8, end: 11 },
  { name: 'I', start: 8, end: 12 },
];

console.log(activitySelection(activities).map(a => a.name));
// ['A', 'D', 'H'] — 3 non-overlapping activities

// Jump Game I — O(n) time, O(1) space
function canJump(nums) {
  let maxReach = 0;

  for (let i = 0; i < nums.length; i++) {
    if (i > maxReach) return false;  // can't reach position i
    maxReach = Math.max(maxReach, i + nums[i]);
  }

  return true;
}

console.log(canJump([2, 3, 1, 1, 4])); // true
console.log(canJump([3, 2, 1, 0, 4])); // false — stuck at index 3

// Jump Game II — O(n) time, O(1) space
function jump(nums) {
  let jumps = 0;
  let currentEnd = 0;   // end of the current jump's reach
  let farthest = 0;     // farthest reachable from current window

  for (let i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);

    if (i === currentEnd) {
      // We've exhausted the current jump's window
      // Must take another jump to reach farthest
      jumps++;
      currentEnd = farthest;

      if (currentEnd >= nums.length - 1) break;
    }
  }

  return jumps;
}

console.log(jump([2, 3, 1, 1, 4])); // 2  (index 0→1→4)
console.log(jump([2, 3, 0, 1, 4])); // 2  (index 0→1→4)

// Gas Station — O(n) time, O(1) space
function canCompleteCircuit(gas, cost) {
  let totalGas = 0;
  let currentGas = 0;
  let startStation = 0;

  for (let i = 0; i < gas.length; i++) {
    const net = gas[i] - cost[i];
    totalGas += net;
    currentGas += net;

    // If we can't reach the next station, reset
    if (currentGas < 0) {
      startStation = i + 1;  // try starting from the next station
      currentGas = 0;
    }
  }

  // If total gas < total cost, no solution
  return totalGas >= 0 ? startStation : -1;
}

console.log(canCompleteCircuit([1,2,3,4,5], [3,4,5,1,2])); // 3
console.log(canCompleteCircuit([2,3,4],     [3,4,3]));      // -1

// Assign Cookies — O(n log n + m log m)
function findContentChildren(g, s) {
  g.sort((a, b) => a - b);  // greed factors, ascending
  s.sort((a, b) => a - b);  // cookie sizes, ascending

  let child = 0;
  let cookie = 0;

  while (child < g.length && cookie < s.length) {
    if (s[cookie] >= g[child]) {
      child++;  // this cookie satisfies this child
    }
    cookie++;   // move to next cookie regardless
  }

  return child;  // number of content children
}

console.log(findContentChildren([1, 2, 3], [1, 1]));    // 1
console.log(findContentChildren([1, 2], [1, 2, 3]));    // 2

// Non-overlapping Intervals — minimum intervals to remove
// Equivalent to: (total - maximum non-overlapping)
function eraseOverlapIntervals(intervals) {
  if (intervals.length === 0) return 0;

  // Sort by end time — greedy: keep intervals that end earliest
  intervals.sort((a, b) => a[1] - b[1]);

  let keep = 1;
  let lastEnd = intervals[0][1];

  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] >= lastEnd) {
      keep++;
      lastEnd = intervals[i][1];
    }
    // else: this interval overlaps — skip (remove) it
  }

  return intervals.length - keep;  // number removed
}

console.log(eraseOverlapIntervals([[1,2],[2,3],[3,4],[1,3]])); // 1 (remove [1,3])
console.log(eraseOverlapIntervals([[1,2],[1,2],[1,2]]));        // 2