Greedy Algorithms

def activity_selection(activities):
    """Select maximum non-overlapping activities.
    activities = list of (start, finish) tuples.
    Greedy strategy: always pick the one that finishes earliest."""
    if not activities:
        return []

    # Sort by finish time — finishing early leaves more room
    sorted_acts = sorted(activities, key=lambda x: x[1])
    selected = [sorted_acts[0]]

    for start, finish in sorted_acts[1:]:
        # Only pick activities that start at or after the last one ends
        if start >= selected[-1][1]:
            selected.append((start, finish))

    return selected

# Example
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9),
              (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
result = activity_selection(activities)
print(f"Selected {len(result)} activities: {result}")
# Selected 4 activities: [(1, 4), (5, 7), (8, 11), (12, 16)]
      

def erase_overlap_intervals(intervals):
    """Find the minimum number of intervals to REMOVE so the
    rest don't overlap. This is the complement of activity selection:
    max non-overlapping = n - min removals.
    
    Same greedy idea: sort by finish time, keep non-overlapping ones."""
    if not intervals:
        return 0

    intervals.sort(key=lambda x: x[1])  # Sort by end time
    kept = 1              # Keep the first interval
    last_end = intervals[0][1]

    for start, end in intervals[1:]:
        if start >= last_end:
            # No overlap — keep this interval
            kept += 1
            last_end = end
        # else: overlaps — skip it (implicitly "remove" it)

    return len(intervals) - kept  # Total - kept = removed
      

def fractional_knapsack(items, capacity):
    """Maximize value with a weight limit. Can take fractions.
    items = list of (weight, value) tuples.
    Greedy: sort by value/weight ratio, take as much of the
    best items as possible."""
    # Sort by value-per-weight ratio, highest first
    items_sorted = sorted(items, key=lambda x: x[1]/x[0], reverse=True)

    total_value = 0.0
    remaining = capacity

    for weight, value in items_sorted:
        if remaining <= 0:
            break
        if weight <= remaining:
            # Take the whole item
            total_value += value
            remaining -= weight
        else:
            # Take a fraction — this is why greedy works here
            # (you can't do this in 0/1 knapsack)
            fraction = remaining / weight
            total_value += value * fraction
            remaining = 0

    return total_value
      

function fractionalKnapsack(items, capacity) {
  // Sort by value-per-weight ratio, highest first
  items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));

  let totalValue = 0;
  let remaining = capacity;

  for (const item of items) {
    if (remaining <= 0) break;

    if (item.weight <= remaining) {
      totalValue += item.value;
      remaining -= item.weight;
    } else {
      totalValue += item.value * (remaining / item.weight);
      remaining = 0;
    }
  }
  return totalValue;
}
      

def can_jump(nums):
    """Can you reach the last index? nums[i] = max jump length from i.
    Greedy: track the farthest index reachable so far.
    If at any point i > farthest, we're stuck."""
    farthest = 0
    for i in range(len(nums)):
        if i > farthest:
            return False  # Can't even reach this position
        # Greedily extend our reach as far as possible
        farthest = max(farthest, i + nums[i])
        if farthest >= len(nums) - 1:
            return True  # Early exit: can already reach the end
    return True
      

def jump(nums):
    """Minimum number of jumps to reach the last index.
    Greedy BFS: each 'level' is a range of indices reachable
    with the same number of jumps. Expand the range greedily."""
    if len(nums) <= 1:
        return 0

    jumps = 0
    current_end = 0    # Farthest we can reach with 'jumps' jumps
    farthest = 0       # Farthest we can reach with 'jumps + 1' jumps

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])

        if i == current_end:
            # We've explored all positions reachable with current jumps
            jumps += 1
            current_end = farthest
            if current_end >= len(nums) - 1:
                break

    return jumps
      

function activitySelection(activities) {
  /**
   * Select maximum non-overlapping activities.
   * activities = array of {start, finish} objects.
   * Greedy: sort by finish time, always pick the earliest finisher.
   */
  if (activities.length === 0) return [];

  // Sort by finish time — earliest finisher first
  const sorted = [...activities].sort((a, b) => a.finish - b.finish);
  const selected = [sorted[0]];

  for (let i = 1; i < sorted.length; i++) {
    // Only pick if this activity starts at or after the last one ended
    if (sorted[i].start >= selected[selected.length - 1].finish) {
      selected.push(sorted[i]);
    }
  }
  return selected;
}

// Example
const acts = [
  {start: 1, finish: 4}, {start: 3, finish: 5}, {start: 0, finish: 6},
  {start: 5, finish: 7}, {start: 3, finish: 9}, {start: 5, finish: 9},
  {start: 6, finish: 10}, {start: 8, finish: 11}, {start: 8, finish: 12},
  {start: 2, finish: 14}, {start: 12, finish: 16}
];
console.log(activitySelection(acts));
// [{start:1,finish:4}, {start:5,finish:7}, {start:8,finish:11}, {start:12,finish:16}]
      

function canJump(nums) {
  /**
   * Can you reach the last index?
   * nums[i] = max jump length from position i.
   * Greedy: track the farthest index reachable so far.
   */
  let farthest = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > farthest) return false; // Can't reach this position
    farthest = Math.max(farthest, i + nums[i]);
    if (farthest >= nums.length - 1) return true; // Early exit
  }
  return true;
}

function minJumps(nums) {
  /**
   * Minimum jumps to reach the end.
   * Greedy BFS: each "level" is a range of reachable indices.
   */
  if (nums.length <= 1) return 0;
  let jumps = 0, currentEnd = 0, farthest = 0;

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

import heapq

def huffman_coding(freq):
    """Build a Huffman tree for optimal prefix-free encoding.
    freq = dict of {symbol: frequency}.
    Greedy: always merge the two lowest-frequency nodes.
    
    Returns a dict of {symbol: binary_code_string}."""
    # Priority queue of (frequency, unique_id, node)
    # unique_id prevents comparison of nodes when frequencies tie
    heap = [(f, i, symbol) for i, (symbol, f) in enumerate(freq.items())]
    heapq.heapify(heap)
    uid = len(heap)

    # Merge nodes until one tree remains
    while len(heap) > 1:
        f1, _, left = heapq.heappop(heap)
        f2, _, right = heapq.heappop(heap)
        merged = (left, right)  # Internal node
        heapq.heappush(heap, (f1 + f2, uid, merged))
        uid += 1

    # Extract codes by traversing the tree
    codes = {}
    def traverse(node, code=""):
        if isinstance(node, str):
            codes[node] = code or "0"  # Single-symbol edge case
            return
        left, right = node
        traverse(left, code + "0")
        traverse(right, code + "1")

    if heap:
        traverse(heap[0][2])
    return codes

# Example
frequencies = {"a": 45, "b": 13, "c": 12, "d": 16, "e": 9, "f": 5}
codes = huffman_coding(frequencies)
for symbol, code in sorted(codes.items()):
    print(f"  '{symbol}': {code}")
# 'a' gets the shortest code (highest frequency)
# 'f' gets the longest code (lowest frequency)
      

import heapq

def min_meeting_rooms(meetings):
    """Find the minimum number of conference rooms needed.
    meetings = list of (start, end) tuples.
    
    Greedy with a min-heap: track when each room becomes free.
    When a new meeting starts, if the earliest-freeing room is
    available, reuse it. Otherwise, allocate a new room.
    
    The heap size at any point = number of rooms in use."""
    if not meetings:
        return 0

    # Sort by start time — process meetings in chronological order
    meetings.sort(key=lambda x: x[0])

    # Min-heap of end times (when each room becomes free)
    rooms = []
    heapq.heappush(rooms, meetings[0][1])  # First meeting gets a room

    for start, end in meetings[1:]:
        if rooms[0] <= start:
            # Earliest-freeing room is available — reuse it
            heapq.heapreplace(rooms, end)  # Pop old end, push new end
        else:
            # All rooms are busy — need a new one
            heapq.heappush(rooms, end)

    return len(rooms)

# Example: a busy Tuesday
meetings = [
    (9, 10),    # Standup
    (9, 11),    # Planning session (overlaps with standup)
    (10, 12),   # Design review
    (11, 13),   # Lunch meeting
    (13, 14),   # 1-on-1
    (14, 15),   # Sprint retro
]

rooms_needed = min_meeting_rooms(meetings)
print(f"Need {rooms_needed} rooms")  # Need 2 rooms
# 9-10 and 9-11 overlap → 2 rooms
# From 11 onward, only 1 room is needed at a time
      

function minMeetingRooms(meetings) {
  /**
   * Minimum conference rooms needed. O(n log n) time.
   * 
   * Alternative approach: event-based sweep line.
   * Mark each start as +1 room needed, each end as -1.
   * Sort all events. The peak concurrent meetings = answer.
   */
  if (meetings.length === 0) return 0;

  const events = [];
  for (const [start, end] of meetings) {
    events.push([start, 1]);   // +1 room at start
    events.push([end, -1]);    // -1 room at end
  }

  // Sort by time. If tied, process ends (-1) before starts (+1)
  // so that a meeting ending at 10:00 frees the room before
  // a meeting starting at 10:00 claims it.
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);

  let rooms = 0, maxRooms = 0;
  for (const [, delta] of events) {
    rooms += delta;
    maxRooms = Math.max(maxRooms, rooms);
  }
  return maxRooms;
}

console.log(minMeetingRooms([[9,10],[9,11],[10,12],[11,13],[13,14]]));
// 2 (9-10 and 9-11 overlap)
      

function huffmanCoding(freq) {
  /**
   * Build Huffman codes from a frequency map.
   * freq = { 'a': 45, 'b': 13, 'c': 12, ... }
   * Returns { 'a': '0', 'b': '101', ... }
   * 
   * Uses a simple sorted-array priority queue (fine for small alphabets).
   * For large alphabets, use a proper min-heap.
   */
  // Build initial nodes sorted by frequency
  let nodes = Object.entries(freq)
    .map(([sym, f]) => ({ freq: f, symbol: sym }))
    .sort((a, b) => a.freq - b.freq);

  if (nodes.length === 1) {
    return { [nodes[0].symbol]: '0' };
  }

  // Merge two lowest-frequency nodes until one tree remains
  while (nodes.length > 1) {
    const left = nodes.shift();
    const right = nodes.shift();
    const merged = { freq: left.freq + right.freq, left, right };

    // Insert merged node in sorted position
    let i = 0;
    while (i < nodes.length && nodes[i].freq <= merged.freq) i++;
    nodes.splice(i, 0, merged);
  }

  // Traverse tree to extract codes
  const codes = {};
  function traverse(node, code) {
    if (node.symbol) {
      codes[node.symbol] = code || '0';
      return;
    }
    if (node.left) traverse(node.left, code + '0');
    if (node.right) traverse(node.right, code + '1');
  }
  traverse(nodes[0], '');
  return codes;
}

const codes = huffmanCoding({ a: 45, b: 13, c: 12, d: 16, e: 9, f: 5 });
console.log(codes);
// 'a' gets shortest code (highest frequency), 'f' gets longest