Solve Your First Greedy Algorithm

Build and fix a greedy algorithm to solve the Activity Selection problem.

Introduction

30 Second Summary

Imagine you have 10 activities to choose from but only enough time for a few. How do you pick the most without any overlaps? This is the type of puzzle competitive programmers solve in seconds during contests.

In this project, you will solve the classic Activity Selection problem using a greedy algorithm in C++. You'll set up a competitive programming environment, watch a wrong greedy approach fail, then fix it with the correct strategy.

What You'll Build

You pipe a list of activities into your terminal, hit Enter, and instantly see the maximum number you can schedule without any overlaps.

By the end of this project, you'll have:

A one-keypress compile workflow in VS Code that lets you iterate on solutions as fast as real contest competitors do.
A working solution that reads activities using fast I/O and outputs the maximum non-overlapping set. You can test it with any input piped straight from the terminal.
Firsthand proof of why greedy strategy choice matters: you'll watch a wrong greedy give answer 1, then fix it to correctly give answer 3.
Secret Mission: Solve a second greedy problem using the event-point sweep technique to find the minimum number of rooms needed to schedule all activities.

Are there any prerequisites?

You need basic C++ knowledge (variables, cout, loops, if statements) and a Mac with Xcode Command Line Tools already installed. If you can write a for loop and print to the console, you're ready.

Before We Start

Before we dive in, let's lock in what you're about to build and why it matters for your IOI preparation.

Set Up Your Competitive Programming Environment

During a contest, you compile and run your code dozens of times per problem. A slow workflow where you manually type compiler commands eats into your thinking time.

In this step, you'll set up VS Code so a single keypress compiles your C++ file with contest-standard flags. This means you can focus on algorithms instead of terminal commands.

In this step, get ready to:

Install the C/C++ extension for syntax highlighting and error detection.
Create a cp-problems folder with a one-keypress build configuration.
Test the setup by compiling and running a C++ file.

Install the C/C++ extension

VS Code needs the C/C++ extension by Microsoft to understand your code, highlight syntax, and flag errors as you type.

Press Cmd+Shift+X to open the Extensions panel in VS Code.
Type C++ in the search bar.
Find the extension called C/C++ by Microsoft (it should be the first result).
Click Install.

After a few seconds, the button changes to a gear icon, confirming the extension is active.

Don't see the extension?

Make sure you typed C++ (with the plus signs) in the search bar. The publisher should say Microsoft directly under the extension name.

help me find the C/C++ extension in VS Code

Create your project folder and configure the build task

You need a dedicated folder for your competitive programming problems. Inside it, a tasks.json file tells VS Code exactly how to compile your C++ files.

Open Terminal on your Mac by pressing Cmd+Space, typing Terminal, and pressing Enter.
Move to your Desktop by running this command:

cd ~/Desktop

Create your project folder and move into it by running these commands:

mkdir cp-problems
cd cp-problems

Open this folder in VS Code by running:

code .

VS Code opens with cp-problems shown in the title bar and an empty Explorer sidebar.

Terminal doesn't recognize the code command?

The code command needs to be added to your PATH first. Open VS Code manually, press Cmd+Shift+P to open the Command Palette, type shell command, and select Shell Command: Install 'code' command in PATH.

Restart your terminal, then try code . again.

help me set up the code command on macOS

Now you'll create the build configuration file that makes one-keypress compiling possible.

In VS Code's Explorer sidebar, click the New Folder icon (the folder icon with a plus sign).
Name the folder .vscode and press Enter.
Click on the .vscode folder to select it, then click the New File icon (the file icon with a plus sign).
Name the file tasks.json and press Enter.
Paste the following build configuration into tasks.json:

{
  "version": "2.0.0",
  "tasks": [
    {
      "type": "cppbuild",
      "label": "Build C++ (CP)",
      "command": "/usr/bin/clang++",
      "args": [
        "-std=c++17",
        "-O2",
        "-Wall",
        "-g",
        "${file}",
        "-o",
        "${fileDirname}/${fileBasenameNoExtension}"
      ],
      "options": {
        "cwd": "${fileDirname}"
      },
      "problemMatcher": ["$gcc"],
      "group": {
        "kind": "build",
        "isDefault": true
      },
      "detail": "Compile active C++ file with C++17 and optimizations"
    }
  ]
}

What does this configuration do?

/usr/bin/clang++ is the C++ compiler that comes with your Mac's Xcode Command Line Tools.
-std=c++17 enables C++17 features, which is the standard used at the IOI and most major contests.
-O2 turns on optimizations so your code runs faster, matching contest judge behavior.
-Wall enables all compiler warnings, catching common mistakes before you submit.
-g includes debug info in case you need to use a debugger.
"isDefault": true makes this the default build task, so Cmd+Shift+B always triggers it.

Save tasks.json with Cmd+S.

✔️ Awesome, I've got everything!

Great. Double check you've saved the file, then move on to test it.

ⓧ I'd like to double check the full code

Your .vscode/tasks.json should look exactly like this:

{
  "version": "2.0.0",
  "tasks": [
    {
      "type": "cppbuild",
      "label": "Build C++ (CP)",
      "command": "/usr/bin/clang++",
      "args": [
        "-std=c++17",
        "-O2",
        "-Wall",
        "-g",
        "${file}",
        "-o",
        "${fileDirname}/${fileBasenameNoExtension}"
      ],
      "options": {
        "cwd": "${fileDirname}"
      },
      "problemMatcher": ["$gcc"],
      "group": {
        "kind": "build",
        "isDefault": true
      },
      "detail": "Compile active C++ file with C++17 and optimizations"
    }
  ]
}

Test the setup with a hello world program

The build configuration is ready, but you need to prove it works. You'll create a tiny C++ program, compile it with one keypress, and run it.

In the Explorer sidebar, click the New File icon at the top level of cp-problems (not inside .vscode).
Name the file hello.cpp and press Enter.
Paste this code into hello.cpp:

#include <iostream>
using namespace std;

int main() {
    // Print a message to confirm the build works
    cout << "Hello, competitive programming!" << endl;
    return 0;
}

What does this code do?

This is the simplest possible C++ program. It includes the iostream library for output, then prints a message to the terminal. If this compiles and runs, your entire build chain is working.

Save hello.cpp with Cmd+S.
Make sure hello.cpp is the active tab (click on it if it's not).
Press Cmd+Shift+B to trigger the build task.

You should see a terminal panel appear at the bottom of VS Code showing the compilation command and a successful exit.

What should I see?

The terminal output shows the clang++ command running with all your flags, followed by a message like "Build finished successfully" or "Terminal will be reused by tasks." No error messages means it compiled correctly.

Now run the compiled program. Before you do, what do you expect to see in the terminal?

Open VS Code's integrated terminal by pressing Ctrl+` (backtick key, top-left of keyboard).
Run the compiled program:

./hello

You should see Hello, competitive programming! printed in the terminal.

Seeing "permission denied" or "no such file"?

If you see "no such file or directory", the build step may have failed silently. Press Cmd+Shift+B again and check the build terminal for error messages.
Make sure hello.cpp was the active file when you pressed Cmd+Shift+B. The build task compiles whichever file is currently open.
If you see a dropdown asking which task to run, select Build C++ (CP).

help me troubleshoot my C++ build task in VS Code

Your competitive programming environment is ready. Every time you press Cmd+Shift+B, VS Code compiles whatever C++ file you have open. Next up, you'll use this setup to read problem input and build your first algorithm.

Read Activities with Vectors and Pairs

Your competitive programming environment is ready. You can compile any C++ file with a single keypress.

Every competitive programming problem starts with reading input into the right data structure. In this step, you'll use vectors (resizable arrays) and pairs (two values stuck together) to store activity data. These two structures appear in almost every contest problem.

In this step, get ready to:

Create a solution file with fast I/O setup for competitive programming.
Read activities into a vector of pairs and print them back to verify correctness.
Test your program by piping input from the terminal.

Create solution.cpp with fast I/O and input reading

The Activity Selection problem gives you N activities, each with a start time and an end time. Your first job is to read them all into memory so you can work with them.

Create a new file called solution.cpp in your cp-problems folder and add the following code:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // Fast I/O for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Read number of activities
    int n;
    cin >> n;

    // Read each activity's start and end time into a vector of pairs
    vector<pair<int, int>> activities(n);
    for (int i = 0; i < n; i++) {
        cin >> activities[i].first >> activities[i].second;
    }

    // Print all activities to confirm input was read correctly
    for (int i = 0; i < n; i++) {
        cout << activities[i].first << " " << activities[i].second << "\n";
    }

    return 0;
}

What does this code do?

ios_base::sync_with_stdio(false) and cin.tie(NULL) disable synchronisation between C and C++ I/O streams. This makes input and output much faster, which matters in contests with large inputs.
vector<pair<int, int>> activities(n) creates a resizable array of N pairs. Each pair holds two integers: a start time (.first) and an end time (.second).
The second for loop prints every activity back out. This is a common contest debugging technique: confirm your input reading works before writing any logic.

Save solution.cpp.

Build and test with piped input

In contests, you test solutions by feeding them input directly from the terminal. You'll pipe a sample test case into your program to confirm it reads and prints correctly.

Make sure solution.cpp is the active tab in VS Code.
Press Cmd+Shift+B to compile.

Before you run the test, think about what you expect. If you feed in 4 activities, what should the program print back?

Run your program with test input by running this command in the integrated terminal:

printf "4\n1 100\n2 3\n4 5\n6 7\n" | ./solution

What does this command do?

printf outputs the text with \n as actual newlines. The | (pipe) sends that output directly into your program as if someone typed it. The first line is 4 (number of activities), followed by 4 lines of start/end pairs.

You should see all 4 activities printed back with their start and end times:

If you see those 4 lines, your input reading works perfectly. The program read all the pairs and echoed them back.

Not seeing the expected output?

If you see a "No such file or directory" error, make sure you compiled first with Cmd+Shift+B. The ./solution file only exists after a successful build.
If you see compile errors, check that your #include lines match exactly: <iostream> and <vector>.
If the output looks garbled or empty, confirm your cin >> lines read into activities[i].first and activities[i].second.

Help me debug my solution.cpp output

✔️ Awesome, I've got everything!

Great. Double check you've saved solution.cpp and move on to the next step.

ⓧ I'd like to double check the full code

Here is the complete solution.cpp file. Make sure yours matches:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<pair<int, int>> activities(n);
    for (int i = 0; i < n; i++) {
        cin >> activities[i].first >> activities[i].second;
    }

    for (int i = 0; i < n; i++) {
        cout << activities[i].first << " " << activities[i].second << "\n";
    }

    return 0;
}

Your program reads input and stores it correctly. Next up, you'll write your first greedy algorithm to select the maximum number of non-overlapping activities.

Try the Wrong Greedy First

Your program can read and print activities. Now it is time to actually solve the problem: given a list of activities, find the maximum number of non-overlapping ones you can schedule.

The most obvious approach is to sort activities by start time and greedily pick the earliest-starting activity that does not overlap with the last one you selected. This feels logical. Let's implement it and see what happens.

In this step, get ready to:

Sort activities by start time using the standard library.
Implement a greedy selection loop that picks non-overlapping activities.
Run the algorithm and observe its output on a test case.

Add the algorithm include and sort by start time

Before you can sort, you need access to the sort() function from the C++ standard library.

In solution.cpp, find the includes at the top of your file:

#include <iostream>
#include <vector>

Add #include <algorithm> directly below #include <vector>, so the top of your file now looks like this:

#include <iostream>
#include <vector>
#include <algorithm>

Now find and delete the print loop at the bottom of your main() function. This is the code to remove:

    for (int i = 0; i < n; i++) {
        cout << activities[i].first << " " << activities[i].second << "\n";
    }

In its place (after the reading loop), add the sort and the greedy algorithm by pasting this code:

    // Sort by start time (the wrong greedy choice)
    sort(activities.begin(), activities.end());

    int count = 1;
    int lastFinish = activities[0].second;

    for (int i = 1; i < n; i++) {
        if (activities[i].first >= lastFinish) {
            count++;
            lastFinish = activities[i].second;
        }
    }

    cout << count << endl;

What does this code do?

sort(activities.begin(), activities.end()) sorts by the first element of each pair (start time) because that is the default comparison for pair in C++. Activities that start earliest come first.

The greedy loop starts by selecting the first activity. It then walks through the rest, selecting each one whose start time is at or after the finish time of the last selected activity. count tracks how many non-overlapping activities were selected.

Save solution.cpp.

✔️ Awesome, I've got everything!

Great. Double check you have saved your file before building.

ⓧ I'd like to double check the full code

Your solution.cpp should contain these sections in order. Scroll up and confirm each is present:

Three includes: <iostream>, <vector>, <algorithm>.
The using namespace std; line.
Fast I/O setup (ios_base::sync_with_stdio(false) and cin.tie(NULL)).
Reading N and the activities into a vector<pair<int, int>>.
The sort call on activities.
The greedy loop with count, lastFinish, and the cout << count << endl at the end.
No print loop remaining from the previous step.

Build and run with the test input

Time to test. Think about the input you are about to feed in: activities (1,100), (2,3), (4,5), (6,7).

Before you run this, what do you think the output will be? How many non-overlapping activities can you schedule from that list?

Build solution.cpp by pressing Cmd+Shift+B.
Run the compiled program with test input by running this command in the integrated terminal:

printf "4\n1 100\n2 3\n4 5\n6 7\n" | ./solution

The output is 1.

But wait. Look at the activities by hand: (2,3), (4,5), and (6,7) all fit together without overlapping. The correct answer is 3, not 1. Your greedy algorithm is broken.

Why did sorting by start time fail?

Sorting by start time put activity (1,100) first because it starts earliest. The greedy loop selected it, and its finish time of 100 blocked every other activity. The algorithm returned 1 because nothing else could fit after an activity that runs from time 1 to time 100.

This is the fundamental lesson of greedy algorithms: the choice of greedy criterion determines whether you get the optimal answer or a terrible one.

Seeing a different number or an error?

If you see a compile error, check that #include <algorithm> is at the top of your file. The sort() function lives in that header.

If you see 0 instead of 1, make sure count starts at 1 (not 0), because the first activity is always selected.

If you still see all four activities printed, you likely did not remove the old print loop from Step 2.

Help me debug my greedy algorithm output.

Your algorithm gives the wrong answer, and now you know exactly why. The greedy chose an activity that started earliest but hogged all the time. In the next step, you will fix this with a single change that turns this broken algorithm into an optimal one.

Fix It with the Correct Greedy

In the last step, your greedy algorithm picked the activity starting at time 1, which happened to end at time 100. That single choice blocked every other activity from fitting.

The fix is surprisingly small. Instead of sorting by start time, you sort by finish time. This ensures the algorithm always picks the activity that ends earliest, leaving maximum room for future activities.

In this step, get ready to:

Replace the default sort with a custom comparator that sorts by finish time.
Run your fixed solution and see the correct answer of 3.
Verify correctness with additional test inputs.

Replace the sort with a custom comparator

The default sort on a vector of pairs sorts by the first element (start time). You need a custom comparator that sorts by the second element (finish time) instead.

In solution.cpp, find the sort section near the middle of your file:

    // Sort by start time (the wrong greedy choice)
    sort(activities.begin(), activities.end());

Replace those two lines with this custom comparator that sorts by finish time:

    // Sort by finish time (the correct greedy choice)
    sort(activities.begin(), activities.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        return a.second < b.second;
    });

What does this comparator do?

The lambda [](const pair<int, int>& a, const pair<int, int>& b) { return a.second < b.second; } is a custom comparison function passed to sort.

It tells the sort to compare pairs by their .second value (the finish time) rather than the default .first (start time). The rest of your greedy loop stays exactly the same.

Save solution.cpp.

✔️ Awesome, I've got everything!

Great. Double check you have saved your file before building.

ⓧ I'd like to double check the full code

Your solution.cpp should have these sections in order:

Three includes at the top: <iostream>, <vector>, <algorithm>.
Fast I/O setup with ios_base::sync_with_stdio(false) and cin.tie(NULL).
Reading N activities into vector<pair<int, int>>.
The new sort call with the lambda comparator sorting by .second.
The greedy selection loop checking activities[i].first >= lastFinish.
Output of count at the end.

Build and test with the original input

Make sure solution.cpp is the active file in VS Code.
Build it by pressing Cmd+Shift+B.

Before you run this, think: if the activities are now sorted by finish time, which activity will the algorithm pick first from (1,100), (2,3), (4,5), (6,7)?

Run your solution with the same test input from the previous step:

printf "4\n1 100\n2 3\n4 5\n6 7\n" | ./solution

You should see 3 printed. The algorithm now picks (2,3), (4,5), and (6,7), skipping the greedy-trap activity (1,100) that ends too late.

Why does finish-time sorting fix the problem?

By always choosing the activity that finishes earliest, you minimise the time "consumed" by each selection. Activity (2,3) finishes at time 3, leaving everything from time 3 onward available.

The start-time sort picked (1,100) first because it started earliest. That consumed all time up to 100, blocking every other activity. One line changed. Three more activities fit.

Still seeing 1 instead of 3?

Make sure your lambda returns a.second < b.second (comparing finish times, the second element of the pair). If you accidentally wrote a.first < b.first, you are still sorting by start time.

Also confirm you saved the file before building. Help me debug my sort comparator for the activity selection problem.

Verify with additional test cases

A single test case is never enough in competitive programming. You should always try edge cases and different input shapes.

Test with an input where one long activity overlaps shorter ones:

printf "3\n1 2\n3 4\n0 6\n" | ./solution

You should see 2. Activities (1,2) and (3,4) fit together, while (0,6) overlaps both.

Test with a single activity (the simplest possible input):

printf "1\n5 9\n" | ./solution

You should see 1. With only one activity, the answer is always 1.

Why test multiple inputs?

In competitive programming contests, your solution must handle all valid inputs within the problem constraints. Testing with different shapes (overlapping intervals, single elements, already-sorted input) helps catch off-by-one errors and edge cases before you submit.

Your greedy algorithm now solves the Activity Selection problem correctly. A single change to the sort criterion turned a broken answer into an optimal one. If you want to push further, a Secret Mission awaits with a completely different greedy technique.

Secret mission

Minimum Rooms Problem

You've solved one greedy problem, but can you apply a completely different greedy technique to a new problem? In this challenge, you'll determine the minimum number of rooms needed to schedule ALL activities, even overlapping ones. This requires the event-point sweep technique.

Clean Up Your Resources

This project runs entirely locally, so there are no ongoing costs. Decide whether to keep your resources for future practice, or delete them entirely.

Resources you used:

The cp-problems folder on your Desktop (contains hello.cpp, solution.cpp, rooms.cpp, compiled executables, and .vscode/tasks.json).
The C/C++ VS Code Extension by Microsoft.

Keep everything running

No action needed. Choose this if you plan to keep practicing competitive programming problems.

Your cp-problems folder is your ongoing practice workspace. Add new .cpp files for each new problem you solve.
The tasks.json build configuration works for any C++ file in the folder. Just open a new file, write your solution, and press Cmd+Shift+B to compile.
The C/C++ extension stays installed in VS Code and helps with any future C++ work.

Pause - I'll come back to this later

Everything is local files with no running processes. There is nothing to pause or shut down.

Your files stay on disk until you choose to delete them.
No background services or servers are running from this project.
When you come back, open the cp-problems folder in VS Code and pick up where you left off.

Delete - I don't want to use this again

Remove all project files and the VS Code extension to start fresh.

Delete the project folder by running this command in your terminal:

rm -rf ~/Desktop/cp-problems

Uninstall the C/C++ extension in VS Code: open Extensions with Cmd+Shift+X, find C/C++ by Microsoft, click the gear icon next to it, and select Uninstall.

Nice Work!

You just solved your first greedy algorithm problem from the IOI syllabus. You went from zero competitive programming setup to a working solution that finds the maximum number of non-overlapping activities.

You've learned how to:

Set up a competitive programming environment in VS Code with one-keypress compile using contest-standard C++17 flags.
Experience why greedy strategy choice matters. The wrong sort criterion gave answer 1, but the right one gave answer 3.
Implement the Activity Selection greedy algorithm, a foundational IOI syllabus topic (AL2), using vectors, pairs, and a custom comparator.
Secret Mission: Solved the Minimum Rooms problem using the event-point sweep technique, a second greedy strategy.

Ready to quiz yourself?