Implementing Advanced Greedy Patterns
1. Solving Huffman Coding
Huffman coding is a classic greedy algorithm used for lossless data compression. It builds a variable-length prefix code that minimizes the total encoded length of a message.
| Component | Description | Details |
|---|---|---|
| Frequency Table | Character frequencies in input data | Each character mapped to its occurrence count |
| Huffman Tree | Binary tree built from frequencies | Leaf nodes represent characters, internal nodes represent merged frequencies |
| Code Assignment | Binary codes for each character | Left edge = 0, Right edge = 1; path from root to leaf |
Example: Building Huffman Tree
const input = "hello world";
// Step 1: Count frequencies
const freqMap = new Map();
for (let char of input) {
freqMap.set(char, (freqMap.get(char) || 0) + 1);
}
// Step 2: Create min-heap of nodes
class Node {
constructor(char, freq, left = null, right = null) {
this.char = char;
this.freq = freq;
this.left = left;
this.right = right;
}
}
const minHeap = [];
for (let [char, freq] of freqMap) {
minHeap.push(new Node(char, freq));
}
// Step 3: Build tree
while (minHeap.length > 1) {
const left = minHeap.shift();
const right = minHeap.shift();
const merged = new Node(null, left.freq + right.freq, left, right);
minHeap.push(merged);
// Re-sort heap by frequency (simplified)
minHeap.sort((a, b) => a.freq - b.freq);
}
// Step 4: Generate codes
const codes = new Map();
function generateCodes(node, code = "") {
if (node.char !== null) {
codes.set(node.char, code);
return;
}
generateCodes(node.left, code + "0");
generateCodes(node.right, code + "1");
}
generateCodes(minHeap[0]);
console.log(codes); // Map with character codesExample: Encoding with Huffman Codes
const input = "hello world";
const codes = new Map([
["h", "1000"],
["e", "1001"],
["l", "00"],
["o", "101"],
[" ", "1100"],
["w", "1101"],
["r", "1110"],
["d", "1111"]
]);
let encoded = "";
for (let char of input) {
encoded += codes.get(char);
}
console.log(encoded); // "1000100100001011100110111101111"
Note: Huffman coding is optimal for a given set of character frequencies, minimizing the expected code length.
2. Implementing Interval Scheduling Variants
| Variant | Description | Key Characteristics | Use Case |
|---|---|---|---|
| Activity Selection | Maximize the number of non-overlapping activities | Greedy by end time; O(n log n) due to sorting | Scheduling meetings, classes, or resource allocation |
| Weighted Interval Scheduling | Maximize total weight of selected non-overlapping intervals | Dynamic programming approach; O(n log n) for sorting + O(n) for DP | Project planning, task scheduling with weights |
| Interval Partitioning | Minimize the number of "resources" to schedule all intervals | Greedy by end time; O(n log n) for sorting + O(n) for partitioning | Resource allocation, meeting room scheduling |
Example: Activity Selection
const activities = [
{ start: 1, end: 3 },
{ start: 2, end: 4 },
{ start: 3, end: 5 },
{ start: 4, end: 6 }
];
function activitySelection(activities) {
// Sort by end time
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++) {
const current = activities[i];
if (current.start >= lastEnd) {
selected.push(current);
lastEnd = current.end;
}
}
return selected;
}
console.log(activitySelection(activities));
// Output: [{ start: 1, end: 3 }, { start: 3, end: 5 }]Example: Weighted Interval Scheduling
const intervals = [
{ start: 1, end: 3, weight: 5 },
{ start: 2, end: 4, weight: 6 },
{ start: 3, end: 5, weight: 7 },
{ start: 4, end: 6, weight: 8 }
];
function weightedIntervalScheduling(intervals) {
// Sort by end time
intervals.sort((a, b) => a.end - b.end);
const n = intervals.length;
const dp = new Array(n).fill(0);
dp[0] = intervals[0].weight;
for (let i = 1; i < n; i++) {
let include = intervals[i].weight;
let lastNonOverlap = -1;
// Find latest non-overlapping interval
for (let j = i - 1; j >= 0; j--) {
if (intervals[j].end <= intervals[i].start) {
lastNonOverlap = j;
break;
}
}
if (lastNonOverlap !== -1) {
include += dp[lastNonOverlap];
}
dp[i] = Math.max(dp[i - 1], include);
}
return dp[n - 1];
}
console.log(weightedIntervalScheduling(intervals));
// Output: 15 (intervals with weights 7 and 8)
Note: For interval scheduling, the greedy approach works optimally for activity selection and interval partitioning. Weighted interval scheduling requires dynamic programming to handle weights.
3. Implementing Fractional Greedy
| Problem Type | Description | Approach | Example |
|---|---|---|---|
| Fractional Knapsack | Items can be broken into fractions. Maximize value within weight limit. | Greedy: Sort by value-to-weight ratio (descending). Take items until weight limit is reached. | |
| Activity Selection | Select maximum number of non-overlapping activities. | Greedy: Sort by finish time. Select first activity, then select next activity that starts after the previous finishes. | |
Example: Fractional Knapsack
const items = [
{ weight: 10, value: 60 },
{ weight: 20, value: 100 },
{ weight: 30, value: 120 }
];
const capacity = 50;
function fractionalKnapsack(items, capacity) {
items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));
let totalValue = 0;
for (const item of items) {
if (item.weight <= capacity) {
totalValue += item.value;
capacity -= item.weight;
} else {
totalValue += (capacity / item.weight) * item.value;
break;
}
}
return totalValue;
}
console.log(fractionalKnapsack(items, capacity)); // Output: 240
Example: Activity Selection
const activities = [
{ name: 'A', start: 1, finish: 4 },
{ name: 'B', start: 3, finish: 5 },
{ name: 'C', start: 0, finish: 6 },
{ name: 'D', start: 5, finish: 7 },
{ name: 'E', start: 3, finish: 9 },
{ name: 'F', start: 5, finish: 9 },
{ name: 'G', start: 6, finish: 10 },
{ name: 'H', start: 8, finish: 11 },
{ name: 'I', start: 8, finish: 12 },
{ name: 'J', start: 2, finish: 14 },
{ name: 'K', start: 12, finish: 16 }
];
function activitySelection(activities) {
activities.sort((a, b) => a.finish - b.finish);
const selected = [activities[0]];
let lastFinish = activities[0].finish;
for (let i = 1; i < activities.length; i++) {
if (activities[i].start >= lastFinish) {
selected.push(activities[i]);
lastFinish = activities[i].finish;
}
}
return selected.map(a => a.name);
}
console.log(activitySelection(activities)); // Output: ['A', 'D', 'G', 'K']
4. Implementing Greedy Coloring
| Property | Description | Usage |
|---|---|---|
| Graph Representation | Adjacency list or matrix to represent nodes and edges | Used in graph coloring algorithms to determine node connections |
| Color Assignment | Assign colors to nodes such that no adjacent nodes share the same color | Greedy approach assigns colors sequentially based on node degree or adjacency |
| Color Set | Set of available colors to use for node coloring | Can be finite or infinite depending on the problem constraints |
Example: Basic Greedy Coloring Algorithm
function greedyColoring(graph) {
const colors = {};
const colorSet = new Set();
// Assign colors to nodes
for (const node in graph) {
const usedColors = new Set();
for (const neighbor of graph[node]) {
if (colors[neighbor] !== undefined) {
usedColors.add(colors[neighbor]);
}
}
let color = 0;
while (usedColors.has(color)) {
color++;
}
colors[node] = color;
colorSet.add(color);
}
return { colors, numColors: colorSet.size };
}
// Example usage
const graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C']
};
const result = greedyColoring(graph);
console.log(result.colors); // { A: 0, B: 1, C: 1, D: 0 }
console.log(result.numColors); // 2
Note: The greedy coloring algorithm does not guarantee the optimal number of colors, but it provides a quick and effective solution for many practical applications.
5. Solving Set Cover Approximation
The Set Cover problem is a classic NP-hard optimization problem where we aim to find the smallest collection of sets from a given collection that covers all elements in the universe. While solving it optimally is computationally expensive, greedy algorithms provide a well-known approximation.
For the Set Cover Approximation, a greedy approach works as follows:
- At each step, select the set that covers the maximum number of uncovered elements.
- Repeat until all elements are covered.
This greedy method provides a logarithmic approximation ratio (specifically, O(log n) where n is the number of elements in the universe).
Example: Set Cover Approximation
const universe = [1, 2, 3, 4, 5];
const sets = [
{ id: 'A', elements: [1, 2, 3] },
{ id: 'B', elements: [2, 4] },
{ id: 'C', elements: [3, 5] },
{ id: 'D', elements: [4, 5] }
];
function greedySetCover(universe, sets) {
const uncovered = new Set(universe);
const selectedSets = [];
while (uncovered.size > 0) {
let bestSet = null;
let maxCoverage = -1;
for (const set of sets) {
const coverage = set.elements.filter(e => uncovered.has(e)).length;
if (coverage > maxCoverage) {
maxCoverage = coverage;
bestSet = set;
}
}
if (!bestSet) break;
selectedSets.push(bestSet);
bestSet.elements.forEach(e => uncovered.delete(e));
}
return selectedSets;
}
const result = greedySetCover(universe, sets);
console.log(result.map(s => s.id)); // Output: ['A', 'B'] or similar| Property | Description | Notes |
|---|---|---|
| Universe | Set of all elements to be covered | Fixed input |
| Sets | Collection of subsets of universe | Input to choose from |
| Approximation Ratio | O(log n) |
Where n is size of universe |
Note: The greedy solution does not guarantee an optimal cover but provides a near-optimal result in polynomial time.
6. Implementing Vertex Cover Approximation
Vertex Cover is a classic NP-hard problem where the goal is to find the smallest set of vertices such that every edge in the graph is incident to at least one vertex in the set.
This section covers a greedy approximation algorithm for Vertex Cover, which provides a 2-approximation to the optimal solution.
Example: Greedy Vertex Cover Approximation
function greedyVertexCover(graph) {
const cover = new Set();
const edges = [...graph.edges];
while (edges.length > 0) {
const edge = edges[0];
const u = edge[0];
const v = edge[1];
cover.add(u);
cover.add(v);
// Remove all edges connected to u or v
const newEdges = [];
for (const e of edges) {
if (e[0] !== u && e[1] !== u && e[0] !== v && e[1] !== v) {
newEdges.push(e);
}
}
edges.length = 0;
edges.push(...newEdges);
}
return Array.from(cover);
}
// Example usage:
const graph = {
edges: [
[0, 1],
[1, 2],
[2, 3],
[3, 4]
]
};
console.log(greedyVertexCover(graph)); // Output: [0, 2, 4]
| Property | Description | Notes |
|---|---|---|
| Approximation Ratio | 2-approximation | At most twice the size of optimal vertex cover |
| Time Complexity | O(E) | Where E is the number of edges in the graph |
| Space Complexity | O(V + E) | Where V is the number of vertices and E is the number of edges |
Note: The greedy approach picks an edge and includes both its endpoints in the cover, then removes all edges connected to these vertices. This ensures that every edge is covered and provides a 2-approximation.
7. Calculating Approximation Ratios
Approximation ratios are used to measure how close an approximate solution is to the optimal solution for NP-hard problems. For a minimization problem, if OPT is the optimal solution and A is the approximate solution, the approximation ratio is defined as:
| Ratio Type | Formula | Description |
|---|---|---|
| Approximation Ratio | max(OPT/A, A/OPT) |
Worst-case ratio for minimization/maximization problems |
| Approximation Factor | A/OPT |
For minimization problems, where A ≤ OPT |
For maximization problems, the ratio is defined as:
| Ratio Type | Formula | Description |
|---|---|---|
| Approximation Factor | A/OPT |
For maximization problems, where A ≥ OPT |
Example: Approximation Ratio for Vertex Cover
The approximation ratio for the greedy vertex cover algorithm is 2. This means that for any input graph, the size of the vertex cover found by the algorithm is at most twice the size of the optimal vertex cover.
// Example: Approximation ratio for vertex cover
const graph = {
edges: [[0,1], [1,2], [2,3]],
vertices: 4
};
// Greedy vertex cover algorithm (simplified)
function greedyVertexCover(graph) {
const cover = new Set();
const edges = [...graph.edges];
while (edges.length > 0) {
const edge = edges.shift();
cover.add(edge[0]);
cover.add(edge[1]);
// Remove all edges connected to selected vertices
const newEdges = [];
for (const e of edges) {
if (!cover.has(e[0]) && !cover.has(e[1])) {
newEdges.push(e);
}
}
edges.length = 0;
edges.push(...newEdges);
}
return cover.size;
}
const approx = greedyVertexCover(graph);
const optimal = 2; // For this example graph, optimal is 2
const ratio = approx / optimal;
console.log(`Approximation Ratio: ${ratio}`); // Output: 2
Note: The approximation ratio is a theoretical measure used to analyze the performance of approximation algorithms. It does not guarantee that the solution will be within this ratio for every instance.
8. Comparing Greedy vs Optimal
| Aspect | Greedy Algorithm | Optimal Algorithm |
|---|---|---|
| Approach | Make locally optimal choices at each step | Consider all possibilities to find global optimum |
| Time Complexity | O(n log n) typically | O(2^n) or higher for exhaustive search |
| Space Complexity | O(1) or O(n) | O(n) or more depending on approach |
| Guarantee | Not always optimal | Always optimal if problem has optimal substructure |
| Use Case | Problems with greedy choice property | Problems requiring global optimization |
When to Use Which?
- Greedy: When local choices lead to global optimum (e.g., activity selection, Huffman coding)
- Optimal: When local choices don't guarantee global optimum (e.g., 0/1 knapsack, TSP)
9. Implementing Activity Selection Advanced
| Property | Description | Usage |
|---|---|---|
| Activity | An event with a start time and end time | Used to model tasks or events in scheduling problems |
| Start Time | Time when an activity begins | Used to sort and compare activities |
| End Time | Time when an activity ends | Used to determine overlap and selection |
Example: Activity Selection with End Time Sorting
const activities = [
{ name: 'Meeting', start: 1, end: 4 },
{ name: 'Lunch', start: 3, end: 5 },
{ name: 'Conference', start: 0, end: 6 },
{ name: 'Workshop', start: 5, end: 7 },
{ name: 'Presentation', start: 3, end: 9 },
];
function activitySelection(activities) {
// Sort by end time
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++) {
const current = activities[i];
if (current.start >= lastEnd) {
selected.push(current);
lastEnd = current.end;
}
}
return selected;
}
console.log(activitySelection(activities));
// Output: [{ name: 'Meeting', start: 1, end: 4 }, { name: 'Lunch', start: 3, end: 5 }, { name: 'Workshop', start: 5, end: 7 }]Example: Activity Selection with Priority
const activities = [
{ name: 'Meeting', start: 1, end: 4, priority: 2 },
{ name: 'Lunch', start: 3, end: 5, priority: 1 },
{ name: 'Conference', start: 0, end: 6, priority: 3 },
{ name: 'Workshop', start: 5, end: 7, priority: 2 },
];
function activitySelectionWithPriority(activities) {
// Sort by end time, then by priority (descending)
activities.sort((a, b) => {
if (a.end === b.end) return b.priority - a.priority;
return a.end - b.end;
});
const selected = [activities[0]];
let lastEnd = activities[0].end;
for (let i = 1; i < activities.length; i++) {
const current = activities[i];
if (current.start >= lastEnd) {
selected.push(current);
lastEnd = current.end;
}
}
return selected;
}
console.log(activitySelectionWithPriority(activities));
// Output: [{ name: 'Meeting', start: 1, end: 4, priority: 2 }, { name: 'Lunch', start: 3, end: 5, priority: 1 }, { name: 'Workshop', start: 5, end: 7, priority: 2 }]
Note: The greedy approach for activity selection ensures maximum number of non-overlapping activities by always selecting the activity with the earliest end time.
10. Solving Minimum Platforms Problem
| Property | Description | Example |
|---|---|---|
| Input | Array of train arrival and departure times | [{"arrival": "09:00", "departure": "09:30"}, {"arrival": "09:10", "departure": "09:40"}] |
| Output | Minimum number of platforms required | 1 |
Example: Minimum Platforms Problem
function minPlatforms(arrivals, departures) {
const n = arrivals.length;
let platforms = 1;
let result = 1;
for (let i = 1; i < n; i++) {
let count = 1;
for (let j = 0; j < i; j++) {
if (arrivals[i] >= departures[j]) {
count++;
}
}
result = Math.max(result, count);
}
return result;
}
const arrivals = ["09:00", "09:10", "10:00"];
const departures = ["09:30", "10:20", "11:00"];
console.log(minPlatforms(arrivals, departures)); // Output: 2
Note: This greedy approach checks all previous trains to determine how many platforms are needed at any given time.