Data Structure Greedy Algorithms Practice Questions with Solutions

By /

Introduction

Greedy Algorithms solve problems by making the best possible choice at each step with the hope of reaching the overall best solution. Instead of reconsidering every previous decision, a greedy approach moves forward with the choice that looks most beneficial at the current moment. In this chapter, you will practice Greedy Algorithms using JavaScript through solved questions covering coin selection, activity selection, fractional knapsack, scheduling, minimum resources, and other practical problems. Data Structure Greedy Algorithms practice questions with solutions help to understand the concepts.

Question 1: Select Maximum Number of Activities

Question

You are given activities with their start and finish times:

let activities = [
    { name: "A", start: 1, finish: 3 },
    { name: "B", start: 2, finish: 5 },
    { name: "C", start: 4, finish: 6 },
    { name: "D", start: 6, finish: 7 },
    { name: "E", start: 5, finish: 8 },
    { name: "F", start: 8, finish: 9 }
];

Select the maximum number of non-overlapping activities.

Solution

The greedy strategy is to always select the activity that finishes earliest.

let activities = [
    { name: "A", start: 1, finish: 3 },
    { name: "B", start: 2, finish: 5 },
    { name: "C", start: 4, finish: 6 },
    { name: "D", start: 6, finish: 7 },
    { name: "E", start: 5, finish: 8 },
    { name: "F", start: 8, finish: 9 }
];

activities.sort((a, b) => a.finish - b.finish);

let selected = [];
let lastFinish = 0;

for (let activity of activities) {
    if (activity.start >= lastFinish) {
        selected.push(activity.name);
        lastFinish = activity.finish;
    }
}

console.log(selected);
console.log("Maximum activities:", selected.length);

Output

["A", "C", "D", "F"]
Maximum activities: 4

The selected activities do not overlap.

Question 2: Find Minimum Number of Coins

Question

You have these coin denominations:

let coins = [10, 5, 2, 1];

Find the minimum number of coins needed to make:

27

Solution

The greedy strategy chooses the largest possible coin at every step.

function minCoins(coins, amount) {
    coins.sort((a, b) => b - a);

    let result = [];

    for (let coin of coins) {
        while (amount >= coin) {
            amount -= coin;
            result.push(coin);
        }
    }

    return result;
}

let coins = [10, 5, 2, 1];

let result = minCoins(coins, 27);

console.log(result);
console.log("Number of coins:", result.length);

Output

[10, 10, 5, 2]
Number of coins: 4

The selected coins add up to:

10 + 10 + 5 + 2 = 27

Question 3: Fractional Knapsack Problem

Question

A bag can carry a maximum weight of 50.

You have:

let items = [
    { name: "A", weight: 10, value: 60 },
    { name: "B", weight: 20, value: 100 },
    { name: "C", weight: 30, value: 120 }
];

Find the maximum value that can be placed in the bag when fractions of items are allowed.

Solution

For Fractional Knapsack, calculate:

value / weight

The item with the highest value per unit weight should be selected first.

let items = [
    { name: "A", weight: 10, value: 60 },
    { name: "B", weight: 20, value: 100 },
    { name: "C", weight: 30, value: 120 }
];

let capacity = 50;

items.sort((a, b) => {
    return (b.value / b.weight) - (a.value / a.weight);
});

let totalValue = 0;

for (let item of items) {
    if (capacity >= item.weight) {
        capacity -= item.weight;
        totalValue += item.value;
    } else {
        let fraction = capacity / item.weight;
        totalValue += item.value * fraction;
        capacity = 0;
        break;
    }
}

console.log("Maximum value:", totalValue);

Output

Maximum value: 240

The bag takes:

A → 10 kg → 60 value
B → 20 kg → 100 value
C → 20 kg → 80 value

Total:

60 + 100 + 80 = 240

Question 4: Assign Jobs to Maximize Profit

Question

You have jobs with deadlines and profits:

let jobs = [
    { id: "A", deadline: 2, profit: 100 },
    { id: "B", deadline: 1, profit: 50 },
    { id: "C", deadline: 2, profit: 20 },
    { id: "D", deadline: 1, profit: 70 }
];

Each job takes one unit of time. Schedule the jobs to maximize profit.

Solution

The greedy strategy is:

  1. Sort jobs by profit.
  2. Try to place each job in the latest available slot before its deadline.
let jobs = [
    { id: "A", deadline: 2, profit: 100 },
    { id: "B", deadline: 1, profit: 50 },
    { id: "C", deadline: 2, profit: 20 },
    { id: "D", deadline: 1, profit: 70 }
];

jobs.sort((a, b) => b.profit - a.profit);

let maxDeadline = Math.max(...jobs.map(job => job.deadline));

let slots = new Array(maxDeadline + 1).fill(null);
let totalProfit = 0;

for (let job of jobs) {
    for (let slot = job.deadline; slot > 0; slot--) {
        if (slots[slot] === null) {
            slots[slot] = job.id;
            totalProfit += job.profit;
            break;
        }
    }
}

console.log("Scheduled jobs:", slots.slice(1));
console.log("Total profit:", totalProfit);

Output

Scheduled jobs: ["D", "A"]
Total profit: 170

Job A earns 100 and job D earns 70, giving a total profit of 170.

Question 5: Minimize the Number of Platforms

Question

Trains arrive and depart at a railway station:

let arrivals = [900, 940, 950, 1100, 1500, 1800];
let departures = [910, 1200, 1120, 1130, 1900, 2000];

Find the minimum number of platforms required so that no train has to wait.

Solution

Sort arrival and departure times separately.

let arrivals = [900, 940, 950, 1100, 1500, 1800];
let departures = [910, 1200, 1120, 1130, 1900, 2000];

arrivals.sort((a, b) => a - b);
departures.sort((a, b) => a - b);

let i = 0;
let j = 0;

let platforms = 0;
let maxPlatforms = 0;

while (i < arrivals.length) {
    if (arrivals[i] < departures[j]) {
        platforms++;
        maxPlatforms = Math.max(maxPlatforms, platforms);
        i++;
    } else {
        platforms--;
        j++;
    }
}

console.log("Minimum platforms:", maxPlatforms);

Output

Minimum platforms: 3

At the busiest moment, three trains need platforms simultaneously.

Question 6: Maximize Number of Items Within a Budget

Question

You have a budget of 1000 and these items:

let items = [
    { name: "Book", price: 250 },
    { name: "Bag", price: 450 },
    { name: "Pen", price: 50 },
    { name: "Bottle", price: 150 },
    { name: "Notebook", price: 100 }
];

Using a greedy approach, buy the maximum number of items without exceeding the budget.

Solution

To maximize the number of items, choose the cheapest available items first.

let items = [
    { name: "Book", price: 250 },
    { name: "Bag", price: 450 },
    { name: "Pen", price: 50 },
    { name: "Bottle", price: 150 },
    { name: "Notebook", price: 100 }
];

let budget = 1000;

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

let selected = [];
let spent = 0;

for (let item of items) {
    if (spent + item.price <= budget) {
        selected.push(item.name);
        spent += item.price;
    }
}

console.log("Selected items:", selected);
console.log("Total spent:", spent);
console.log("Number of items:", selected.length);

Output

Selected items: ["Pen", "Notebook", "Bottle", "Book"]
Total spent: 550
Number of items: 4

The items are selected from the lowest price upward.

Question 7: Find Maximum Number of Meetings

Question

A conference room can host only one meeting at a time.

Given:

let meetings = [
    { name: "M1", start: 9, end: 10 },
    { name: "M2", start: 9, end: 11 },
    { name: "M3", start: 10, end: 12 },
    { name: "M4", start: 11, end: 13 },
    { name: "M5", start: 12, end: 14 }
];

Find the maximum number of meetings that can be conducted.

Solution

Sort meetings by their ending time.

let meetings = [
    { name: "M1", start: 9, end: 10 },
    { name: "M2", start: 9, end: 11 },
    { name: "M3", start: 10, end: 12 },
    { name: "M4", start: 11, end: 13 },
    { name: "M5", start: 12, end: 14 }
];

meetings.sort((a, b) => a.end - b.end);

let selected = [];
let lastEnd = -Infinity;

for (let meeting of meetings) {
    if (meeting.start >= lastEnd) {
        selected.push(meeting.name);
        lastEnd = meeting.end;
    }
}

console.log("Selected meetings:", selected);
console.log("Maximum meetings:", selected.length);

Output

Selected meetings: ["M1", "M3", "M5"]
Maximum meetings: 3

The room hosts three non-overlapping meetings.

Question 8: Give Change Using the Largest Coins First

Question

A vending machine needs to return 63 as change.

Available coins are:

[25, 10, 5, 1]

Use a greedy approach to find the coins returned.

Solution

function getChange(coins, amount) {
    coins.sort((a, b) => b - a);

    let change = [];

    for (let coin of coins) {
        while (amount >= coin) {
            amount -= coin;
            change.push(coin);
        }
    }

    return change;
}

let coins = [25, 10, 5, 1];

console.log(getChange(coins, 63));

Output

[25, 25, 10, 1, 1, 1]

The total is:

25 + 25 + 10 + 1 + 1 + 1 = 63

So the machine returns six coins.

Question 9: Select Maximum Compatible Tasks

Question

A person wants to complete as many tasks as possible during the day.

let tasks = [
    { name: "Task A", start: 1, end: 4 },
    { name: "Task B", start: 3, end: 5 },
    { name: "Task C", start: 0, end: 6 },
    { name: "Task D", start: 5, end: 7 },
    { name: "Task E", start: 8, end: 9 },
    { name: "Task F", start: 5, end: 9 }
];

Select the maximum number of non-overlapping tasks.

Solution

Use the same greedy principle: choose the task that finishes earliest.

let tasks = [
    { name: "Task A", start: 1, end: 4 },
    { name: "Task B", start: 3, end: 5 },
    { name: "Task C", start: 0, end: 6 },
    { name: "Task D", start: 5, end: 7 },
    { name: "Task E", start: 8, end: 9 },
    { name: "Task F", start: 5, end: 9 }
];

tasks.sort((a, b) => a.end - b.end);

let selected = [];
let lastEnd = -Infinity;

for (let task of tasks) {
    if (task.start >= lastEnd) {
        selected.push(task.name);
        lastEnd = task.end;
    }
}

console.log(selected);
console.log("Maximum tasks:", selected.length);

Output

["Task A", "Task D", "Task E"]
Maximum tasks: 3

The selected tasks do not overlap.

Question 10: Minimum Number of Notes for an Amount

Question

Write a reusable greedy function to find the minimum number of currency notes needed for an amount.

Use:

Amount = 186
Notes = [100, 50, 20, 10, 5, 1]

Solution

function minimumNotes(notes, amount) {
    notes.sort((a, b) => b - a);

    let result = [];

    for (let note of notes) {
        while (amount >= note) {
            amount -= note;
            result.push(note);
        }
    }

    return result;
}

let notes = [100, 50, 20, 10, 5, 1];

let result = minimumNotes(notes, 186);

console.log(result);
console.log("Number of notes:", result.length);

Output

[100, 50, 20, 10, 5, 1]
Number of notes: 6

The total is:

100 + 50 + 20 + 10 + 5 + 1 = 186

The greedy approach selects the largest possible note at every step.

Key Takeaways

  • A Greedy Algorithm makes the best available choice at each step.
  • The goal is to build a good or optimal solution through local decisions.
  • Greedy Algorithms do not normally reconsider earlier choices.
  • Activity Selection uses the activity with the earliest finish time.
  • Fractional Knapsack selects items based on the highest value-to-weight ratio.
  • Job Sequencing can select jobs based on their profit and deadlines.
  • Coin and note problems can sometimes be solved efficiently using the largest denomination first.
  • Greedy solutions are not guaranteed to work for every problem.
  • Whether a greedy approach is correct depends on the mathematical properties of the problem.
  • Sorting is often an important step in greedy solutions.
  • Greedy Algorithms can provide efficient solutions to many scheduling and optimization problems.
  • A common challenge is identifying the correct greedy rule before writing the code.

FAQs

1. What is a Greedy Algorithm in Data Structures?

A Greedy Algorithm solves a problem by making the best-looking choice at the current step without normally reconsidering previous decisions.

2. How does a Greedy Algorithm work?

The algorithm repeatedly selects the locally best option until the problem is completed or no more valid choices are available.

3. Is every Greedy Algorithm guaranteed to find the optimal solution?

No. A greedy strategy works optimally only for problems that have the appropriate properties, such as the greedy-choice property and optimal substructure.

4. What is the Activity Selection problem?

Activity Selection is a scheduling problem where the objective is to select the maximum number of non-overlapping activities. A standard greedy solution selects activities by earliest finishing time.

5. What is the Fractional Knapsack problem?

Fractional Knapsack asks you to maximize the value placed in a limited-capacity bag when fractions of items are allowed. A greedy strategy sorts items by value per unit weight.

6. What is the difference between Greedy Algorithms and Dynamic Programming?

Greedy Algorithms make a local choice and move forward, while Dynamic Programming generally solves and stores results of overlapping subproblems and considers alternative choices.

7. Where are Greedy Algorithms commonly used?

Greedy techniques are commonly used in scheduling, resource allocation, optimization, minimum spanning trees, shortest-path algorithms under suitable conditions, and some coin-change problems.

Written by Shubhranshu Shekhar, who has trained 20000+ students in coding.

Related Posts

Scroll to Top