Using Greedy Algorithms

1. Applying Greedy Choice Property

Property	Description	Application
Locally Optimal Choice	At each step, make the choice that looks best at the moment	Used in algorithms like Huffman coding, activity selection
Global Optimization	Assumes that local choices lead to a globally optimal solution	Applicable in problems where greedy approach guarantees best result
No Backtracking	Once a choice is made, it's never reconsidered	Used in Dijkstra’s shortest path, Kruskal’s MST

Example: Activity Selection Problem

const activities = [
  { name: 'A1', start: 0, end: 6 },
  { name: 'A2', start: 3, end: 4 },
  { name: 'A3', start: 1, end: 2 },
  { name: 'A4', start: 5, end: 7 },
  { name: 'A5', start: 8, end: 9 },
  { name: 'A6', start: 5, end: 9 }
];

function selectActivities(activities) {
  // Sort by finish time
  activities.sort((a, b) => a.end - b.end);
  const selected = [activities[0]];
  
  for (let i = 1; i < activities.length; i++) {
    if (activities[i].start >= selected[selected.length - 1].end) {
      selected.push(activities[i]);
    }
  }
  
  return selected;
}

console.log(selectActivities(activities));
// Output: [{ name: 'A3', start: 1, end: 2 }, { name: 'A2', start: 3, end: 4 }, { name: 'A4', start: 5, end: 7 }, { name: 'A5', start: 8, end: 9 }]

Note: The greedy choice property is fundamental to problems where making a locally optimal choice at each step leads to a globally optimal solution. This property must be proven for the greedy approach to be valid.

2. Solving Activity Selection

Property	Description	Usage
Activity	An event with a start time and end time	Represented as `[start, end]`
Activity Set	Collection of activities with start and end times	Input for greedy selection algorithm
Compatible Activities	Activities that do not overlap in time	Selected to maximize count without conflict

Example: Selecting Non-Overlapping Activities

const activities = [
  [1, 4],
  [3, 5],
  [0, 6],
  [5, 7],
  [3, 9],
  [5, 9],
  [6, 10],
  [8, 11],
  [8, 12],
  [2, 13],
  [12, 14]
];

function activitySelection(activities) {
  // Sort by end time
  activities.sort((a, b) => a[1] - b[1]);
  
  const selected = [activities[0]];
  let lastEnd = activities[0][1];
  
  for (let i = 1; i < activities.length; i++) {
    const [start, end] = activities[i];
    if (start >= lastEnd) {
      selected.push(activities[i]);
      lastEnd = end;
    }
  }
  
  return selected;
}

console.log(activitySelection(activities));
// Output: [[1, 4], [5, 7], [8, 11], [12, 14]]

Note: The greedy approach of selecting activities that end earliest maximizes the number of compatible activities.

Key Points

Select activities based on earliest finish time
Sort all activities by end time
Iterate and pick compatible ones
Time complexity: O(n log n) due to sorting

3. Solving Fractional Knapsack

The Fractional Knapsack problem involves selecting items with given weights and values to maximize the total value within a weight capacity. Unlike the 0/1 Knapsack problem, items can be broken into fractions.

Property	Description	Value
Problem Type	Optimization problem	Maximize value within weight constraint
Approach	Greedy algorithm	Sort items by value-to-weight ratio
Time Complexity	Sorting + iteration	O(n log n)
Space Complexity	Additional space for sorting	O(1)

Example: Solving Fractional Knapsack

function fractionalKnapsack(capacity, weights, values) {
  const n = weights.length;
  const items = [];

  for (let i = 0; i < n; i++) {
    items.push({
      value: values[i],
      weight: weights[i],
      ratio: values[i] / weights[i]
    });
  }

  items.sort((a, b) => b.ratio - a.ratio);

  let totalValue = 0;
  let remainingCapacity = capacity;

  for (const item of items) {
    if (item.weight <= remainingCapacity) {
      totalValue += item.value;
      remainingCapacity -= item.weight;
    } else {
      const fraction = remainingCapacity / item.weight;
      totalValue += item.value * fraction;
      break;
    }
  }

  return totalValue;
}

// Example usage:
const capacity = 50;
const weights = [10, 20, 30];
const values = [60, 100, 120];

console.log(fractionalKnapsack(capacity, weights, values)); // Output: 240

Note: The greedy approach works optimally for the Fractional Knapsack problem because we can take partial items. For 0/1 Knapsack, dynamic programming is required.

4. Solving Jump Game

Property	Description	Example
jumpGame	Function to determine if you can jump to the end of the array	`jumpGame([2,3,1,1,4])`
maxReach	Maximum index reachable at any point	`maxReach = Math.max(maxReach, i + nums[i])`

Example: Jump Game Solution

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

Note: The greedy approach works by always jumping to the farthest possible position at each step.

5. Solving Jump Game II

The Jump Game II problem involves finding the minimum number of jumps needed to reach the end of an array, where each element represents the maximum jump length from that position.

Property	Description	Value
Input	Array of integers where each element represents the maximum jump length	`[2, 3, 1, 1, 4]`
Output	Minimum number of jumps to reach the end	`2`

Example: Jump Game II Solution

function jump(nums) {
    let jumps = 0;
    let currentEnd = 0;
    let farthest = 0;

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

    return jumps;
}

// Example usage:
const nums = [2, 3, 1, 1, 4];
console.log(jump(nums)); // Output: 2

Note: The greedy approach works by always making the locally optimal choice (jumping as far as possible within current reach) to achieve a globally optimal solution.

6. Solving Gas Station

The Gas Station problem involves determining the starting gas station from which a car can complete a circular route. The car has an unlimited capacity tank and starts with an empty tank.

Property	Description	Notes
gas	Array of integers representing the amount of gas available at each station.	Length is equal to the number of stations.
cost	Array of integers representing the cost (in gas) to travel from each station to the next.	Length is equal to the number of stations.
start	Index of the starting station that allows completing the circuit.	Returns -1 if no such station exists.

Example: Gas Station Problem

function canCompleteCircuit(gas, cost) {
    let totalGas = 0;
    let currentGas = 0;
    let startStation = 0;

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

        if (currentGas < 0) {
            startStation = i + 1;
            currentGas = 0;
        }
    }

    return totalGas >= 0 ? startStation : -1;
}

// Example usage:
const gas = [1, 2, 3, 4, 5];
const cost = [3, 4, 5, 1, 2];
console.log(canCompleteCircuit(gas, cost)); // Output: 3

Note: The greedy approach works because if the total gas is sufficient to cover the total cost, there must exist a starting point from which the journey can be completed. The algorithm tracks the cumulative gas and resets the starting station whenever the tank becomes negative.

7. Solving Task Scheduler

The Task Scheduler problem involves scheduling tasks with cooldown periods to minimize the total time needed to complete all tasks.

Property	Description	Example
Task	Each task has a name and frequency	`A: 3, B: 2, C: 1`
Cool Down Period	Minimum time between same tasks	`2`
Result	Minimum time to complete all tasks	`8`

Example: Task Scheduler Implementation

function leastInterval(tasks, n) {
    const taskCount = {};
    for (const task of tasks) {
        taskCount[task] = (taskCount[task] || 0) + 1;
    }

    const maxHeap = new MaxHeap();
    Object.values(taskCount).forEach(count => maxHeap.insert(count));

    let time = 0;
    const queue = [];

    while (!maxHeap.isEmpty() || queue.length > 0) {
        time++;

        if (!maxHeap.isEmpty()) {
            const count = maxHeap.extractMax() - 1;
            queue.push({ count, time: time + n });
        }

        if (queue.length > 0 && queue[0].time === time) {
            const task = queue.shift();
            if (task.count > 0) maxHeap.insert(task.count);
        }
    }

    return time;
}

class MaxHeap {
    constructor() {
        this.heap = [];
    }

    insert(val) {
        this.heap.push(val);
        this.bubbleUp(this.heap.length - 1);
    }

    bubbleUp(index) {
        if (index === 0) return;
        const parentIndex = Math.floor((index - 1) / 2);
        if (this.heap[parentIndex] < this.heap[index]) {
            [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
            this.bubbleUp(parentIndex);
        }
    }

    extractMax() {
        if (this.heap.length === 0) return null;
        const max = this.heap[0];
        const last = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = last;
            this.sinkDown(0);
        }
        return max;
    }

    sinkDown(index) {
        const left = 2 * index + 1;
        const right = 2 * index + 2;
        let maxIndex = index;

        if (left < this.heap.length && this.heap[left] > this.heap[maxIndex]) {
            maxIndex = left;
        }

        if (right < this.heap.length && this.heap[right] > this.heap[maxIndex]) {
            maxIndex = right;
        }

        if (maxIndex !== index) {
            [this.heap[index], this.heap[maxIndex]] = [this.heap[maxIndex], this.heap[index]];
            this.sinkDown(maxIndex);
        }
    }

    isEmpty() {
        return this.heap.length === 0;
    }
}

// Example usage:
const tasks = ["A", "A", "A", "B", "B", "B"];
const n = 2;
console.log(leastInterval(tasks, n)); // Output: 8

8. Solving Partition Labels

Partition labels is a classic greedy algorithm problem where we need to partition a string into as many parts as possible such that each letter appears in only one part.

Property	Description	Example
Input	String to be partitioned	`"ababcbacadefegdehijhklij"`
Output	List of partition sizes	`[9, 7, 8]`

Example: Partition Labels

function partitionLabels(s) {
    const last = {};
    for (let i = 0; i < s.length; i++) {
        last[s[i]] = i;
    }

    const result = [];
    let start = 0, end = 0;

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

    return result;
}

// Example usage:
console.log(partitionLabels("ababcbacadefegdehijhklij")); // [9, 7, 8]

Note: The key insight is to track the last occurrence of each character and extend the current partition until we reach the furthest last occurrence.

9. Solving Meeting Rooms II

Given an array of meeting time intervals where intervals[i] = [start<sub>i</sub>, end<sub>i</sub>], return the minimum number of conference rooms required.

Input	Description	Example
intervals	Array of intervals, each interval is [start, end]	`[[0,30],[5,10],[15,20]]`

Example 1:

Input: [[0,30],[5,10],[15,20]]
Output: 2
Explanation: One room can host [0,30], another [5,10] and [15,20].

Example 2:

Input: [[7,10],[2,4]]
Output: 1
Explanation: No overlap, so one room suffices.

Approach: Use a min-heap to track the end times of meetings. For each meeting, if the earliest ending meeting has ended before the current one starts, reuse that room. Otherwise, allocate a new room.

Step	Action	Heap State
1	Sort intervals by start time	`[0,30]`
2	Push `30` to heap	`[30]`
3	Compare `5` with top of heap `30`	`[10, 30]`
4	Compare `15` with top of heap `10`	`[20, 30]`

Note: The number of rooms needed equals the maximum size of the heap during processing.

function minMeetingRooms(intervals) {
    if (intervals.length === 0) return 0;

    intervals.sort((a, b) => a[0] - b[0]);

    const minHeap = new MinHeap();
    minHeap.push(intervals[0][1]);

    for (let i = 1; i < intervals.length; i++) {
        const currentStart = intervals[i][0];
        const earliestEnd = minHeap.peek();

        if (currentStart >= earliestEnd) {
            minHeap.pop(); // Reuse room
        }

        minHeap.push(intervals[i][1]);
    }

    return minHeap.size();
}

class MinHeap {
    constructor() {
        this.heap = [];
    }

    push(val) {
        this.heap.push(val);
        this.bubbleUp(this.heap.length - 1);
    }

    pop() {
        if (this.heap.length === 0) return null;
        const min = this.heap[0];
        const last = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = last;
            this.bubbleDown(0);
        }
        return min;
    }

    peek() {
        return this.heap[0];
    }

    size() {
        return this.heap.length;
    }

    bubbleUp(index) {
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.heap[parentIndex] <= this.heap[index]) break;
            [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
            index = parentIndex;
        }
    }

    bubbleDown(index) {
        const len = this.heap.length;
        while (true) {
            const leftChild = 2 * index + 1;
            const rightChild = 2 * index + 2;
            let minIndex = index;

            if (leftChild < len && this.heap[leftChild] < this.heap[minIndex]) {
                minIndex = leftChild;
            }

            if (rightChild < len && this.heap[rightChild] < this.heap[minIndex]) {
                minIndex = rightChild;
            }

            if (minIndex === index) break;
            [this.heap[index], this.heap[minIndex]] = [this.heap[minIndex], this.heap[index]];
            index = minIndex;
        }
    }
}

10. Solving Remove K Digits

Given a non-negative integer represented as a string num, remove k digits to make the resulting number as small as possible.

Property	Description	Example
Input	String representation of a non-negative integer	`"1432219"`
k	Number of digits to remove	`3`
Output	Smallest possible integer after removing `k` digits	`"1221"`

Example: Remove K Digits

function removeKdigits(num, k) {
    const stack = [];
    const toRemove = k;
    
    for (let i = 0; i < num.length; i++) {
        const digit = num[i];
        
        while (stack.length > 0 && stack[stack.length - 1] > digit && toRemove > 0) {
            stack.pop();
            toRemove--;
        }
        
        if (stack.length > 0 || digit !== '0') {
            stack.push(digit);
        }
    }
    
    while (toRemove > 0) {
        stack.pop();
        toRemove--;
    }
    
    return stack.length === 0 ? "0" : stack.join("");
}

// Example usage:
console.log(removeKdigits("1432219", 3)); // "1221"
console.log(removeKdigits("10200", 1));   // "200"
console.log(removeKdigits("10", 2));      // "0"

Note: The greedy approach works by removing larger digits when a smaller digit is found, ensuring the smallest possible number is formed.

11. Solving Candy Distribution

Given a list of children's ratings, distribute candies such that:

Each child gets at least one candy.
A child with a higher rating than their neighbor(s) gets more candies.

Property	Description	Example
ratings	List of integers representing children's ratings	`[1, 0, 2]`
candies	Minimum number of candies to distribute	`5`

Example: Candy Distribution

function candy(ratings) {
  const n = ratings.length;
  const candies = new Array(n).fill(1);

  // Left to right pass
  for (let i = 1; i < n; i++) {
    if (ratings[i] > ratings[i - 1]) {
      candies[i] = candies[i - 1] + 1;
    }
  }

  // Right to left pass
  for (let i = n - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1]) {
      candies[i] = Math.max(candies[i], candies[i + 1] + 1);
    }
  }

  return candies.reduce((sum, count) => sum + count, 0);
}

// Example usage
const ratings = [1, 0, 2];
console.log(candy(ratings)); // Output: 5

Note: The greedy approach ensures each child gets the minimum required candies while satisfying neighbor constraints.

12. Solving Minimum Arrows

Given a set of intervals on the number line, the goal is to determine the minimum number of arrows needed to shoot all intervals. This problem can be solved efficiently using a greedy algorithm by sorting the intervals and selecting the optimal arrow positions.

Step	Description	Action
1	Sort intervals by their end points	Arrange all intervals in ascending order of their end points.
2	Initialize arrow count and last arrow position	Start with 1 arrow and set the position to the end of the first interval.
3	Iterate through sorted intervals	For each interval, if its start is greater than the last arrow position, increment arrow count and update arrow position.

Example: Minimum Arrows to Shoot Balloons

const findMinArrowShots = (points) => {
  if (points.length === 0) return 0;

  // Sort intervals by end point
  points.sort((a, b) => a[1] - b[1]);

  let arrows = 1;
  let lastArrowPosition = points[0][1];

  for (let i = 1; i < points.length; i++) {
    const [start, end] = points[i];
    if (start > lastArrowPosition) {
      arrows++;
      lastArrowPosition = end;
    }
  }

  return arrows;
};

// Example usage:
const points = [[10,16], [2,8], [1,6], [7,12]];
console.log(findMinArrowShots(points)); // Output: 2

Algorithm Summary

Approach: Greedy algorithm using interval sorting
Time Complexity: O(n log n) due to sorting
Space Complexity: O(1)