Module assignment: conference day planner

The brief

You are helping organise a one-day conference. The day has three problems, and each one is a greedy problem from this module.

The first problem is the main stage. Talks are booked as time windows, and the stage can show only one talk at a time. The organiser wants to show as many talks as possible, with no two talks clashing. This is activity selection from lesson 1.

The second problem is the rooms. Every talk needs a room while it runs, and a room is free again the moment its talk ends. The organiser needs to know the fewest rooms that hold every talk. This needs the overlap count, which lesson 1 mentioned and lesson 3 solved with a heap.

The third problem is the setup. Before the day starts, the team must prepare some jobs for the stage. Each setup job takes one hour, has a deadline, and is worth a profit to the team. The team can do one job per hour, starting at hour 1. The team wants the most profit it can get. This is job sequencing from lesson 2.

You will write one program that reads the whole day's plan and prints three answers. You may solve the three parts in any order, but the final program must print all three lines, in the order shown below. The four runnable blocks in this lesson give you the three parts separately, plus a starter, so you can build the program a piece at a time.

What you are given

The input has two sections. The first section lists the talks. The second section lists the setup jobs.

The first line holds n, the number of talks. Each of the next n lines holds one talk: its start time, then its finish time. A talk is the time window from start to finish, and it includes the start moment but not the finish moment. So a talk from 9 to 10 uses the room from 9 up to, but not including, 10. Another talk may start at 10 in the same room.

After the talks, one line holds m, the number of setup jobs. Each of the next m lines holds one job: its deadline, then its profit. The deadline is the last hour in which the job may run, counting hours from 1.

Here is the input shape:

n
start finish      (n lines, one per talk)
m
deadline profit   (m lines, one per job)

You may assume 1 <= n <= 100000, 0 <= m <= 2000, start times and finish times are from 0 to 1000000000 with start less than finish, deadlines are at least 1, and profits are from 0 to 1000000000.

What to print

Print exactly three lines, in this format:

stage talks: K
rooms needed: R
setup profit: P

K is the largest number of talks the stage can show without a clash. R is the fewest rooms needed. P is the largest total profit from the setup jobs.

Spelling, spaces and the colon matter. A judge compares the text exactly, so Stage talks: 4 would be wrong even if the number is right.

The examples

Work through these three examples before you write any code. The outputs come from the reference solution at the end of this lesson, and they were checked with an independent check, so you can trust them as a target.

Example A. This is the example you will use in the four runnable blocks.

5
9 10
10 11
9 12
11 13
8 9
4
1 5
2 3
2 5
1 2

The output is:

stage talks: 4
rooms needed: 2
setup profit: 10

Example B. A single talk and no setup jobs. The input is short, so type it by hand and check the three lines.

1
0 1
0

The output is:

stage talks: 1
rooms needed: 1
setup profit: 0

Example C. Three talks, two of which overlap, and two setup jobs with the same deadline.

3
0 5
5 10
0 10
2
1 4
1 6

The output is:

stage talks: 2
rooms needed: 2
setup profit: 6

Check Example C by hand. For the stage, the talks 0 5 and 5 10 do not clash, so both are shown, and 0 10 clashes with both. For the rooms, at time 0 two talks start, so two rooms are needed. For the setup, the job with profit 6 takes hour 1, and the job with profit 4 has no free hour, because hour 1 is taken and its deadline is hour 1. The setup profit is 6.

Starting point: the skeleton

Start from the skeleton below. It reads the whole input into two lists, then prints three zeros. Compile it and run it on Example A. You should see the three zeros, which proves that the input is being read in the right shape. Then you replace each zero with a real answer.

Type Example A into the Input box, then press Run.

The output you should see:

stage talks: 0
rooms needed: 0
setup profit: 0

The skeleton stores the talks and the jobs as pairs. A pair holds two values, and first and second name them. This is simple, but it hides which number is which, so when you solve each part, copy the values into a struct with clear names, such as start and finish, as the solutions below do.

Part 1: the stage

The stage problem is activity selection. Sort the talks by finish time. Walk down the sorted list with lastFinish set to -1. Take a talk when its start is at or after lastFinish, and update lastFinish to its finish. Count the talks you take.

The run below does Part 1 only. It reads the talks, applies the greedy rule, and prints the first line. Type Example A and press Run.

The output you should see:

stage talks: 4

Check the answer by hand for Example A. Sorted by finish, the talks are 8 9, 9 10, 10 11, 9 12 and 11 13. The walk takes 8 9, then 9 10 (9 is at or after 9), then 10 11, then skips 9 12 (9 is before 11), then takes 11 13. The count is 4.

Two points matter for a high mark. First, the comparator must use < and must compare finish times, not start times. Second, the test is >=, not >, so a talk that starts exactly when another ends is allowed.

Part 2: the rooms

The room problem is the overlap count. Make two events for each talk: a start event with +1 and an end event with -1. Sort all events by time. At the same time, put the -1 event first, because a room that frees up at a moment can be reused by a talk starting at that moment. Walk the sorted events, add each +1 or -1 to a running count, and keep the largest count. That largest count is the number of rooms.

The run below does Part 2 only. Type Example A and press Run.

The output you should see:

rooms needed: 2

Check it by hand for Example A. At time 9, the talk 8 9 has already ended, so the -1 for it comes first. Then the talks starting at 9 are added: 9 10 and 9 12. At that point two talks are running. At time 10, the talk 9 10 ends first, then 10 11 starts, so two talks are running again. The largest number at any moment is 2, so two rooms are enough.

Part 2 is a good example of why sorting events with a clear tie rule matters. If you sort the +1 events before the -1 events at the same time, the program counts a room as busy at the moment it is freed, and it asks for one room too many.

Part 3: the setup

The setup problem is job sequencing. Sort the jobs by profit, highest first. For each job, look for the latest free hour that is at or before its deadline, and cap the search at m, the number of jobs. If you find one, take it and add the profit. If you do not, skip the job.

The run below does Part 3 only. It reads and skips the talks, then reads the jobs and prints the third line. Type Example A and press Run.

The output you should see:

setup profit: 10

Check it by hand for Example A. The jobs are 1 5, 2 3, 2 5 and 1 2, written as deadline and profit. Sorted by profit, the order is 1 5, 2 5, 2 3, 1 2, where the two jobs with profit 5 may come in either order without changing the total. Hour 1 takes the job 1 5. The job 2 5 takes hour 2, the latest free hour at or before its deadline. The job 2 3 finds hours 1 and 2 taken, so it is skipped. The job 1 2 finds hour 1 taken, so it is skipped. The total is 5 plus 5, which is 10.

The int skip loop in this program reads the talk lines and throws them away. In your final program, you will read the talks once and use them for Parts 1 and 2, so you should not read the input twice.

The requirements checklist

Use this list to check your final program before you submit it. Each line should be true.

• The program reads all talks and all jobs from the input in the shape shown above.
• The first output line is stage talks: K with K from the activity selection rule.
• The stage rule sorts by finish time and tests start >= lastFinish.
• The second output line is rooms needed: R with R from the sweep over start and end events.
• The sweep puts an end event before a start event at the same time.
• The third output line is setup profit: P with P from job sequencing.
• The job rule sorts by profit, highest first, and places each job in the latest free hour.
• The job search is capped at m, so a deadline larger than m does not run off the array.
• Each sum uses long long where the total can be large.
• The program passes Examples A, B and C, character for character.
• You have written at least two extra inputs of your own and checked the outputs by hand.
• You can state the complexity of each part and of the whole program.
• Variable names describe the idea, such as lastFinish, rooms and used.

The grading rubric

The rubric describes what the three levels of work look like. Your score depends on the parts that are correct, the edge cases you handle, and how well you explain the rules.

At 60 percent, the program compiles and prints three lines in the right format for Example A. At least one part gives the right answer on every example. The code may fail on edge cases such as touching talks, zero setup jobs, or deadlines larger than the number of jobs. The explanation of the rules is short, and the complexity is missing or wrong for one part.

At 80 percent, the program passes all three examples exactly. All three parts use the right greedy rule, with the right sort key and the right tie rule. The code handles zero setup jobs and touching talks correctly, and it caps the job search at m. The explanation names the rule for each part and says why it is correct, and it gives the complexity of each part.

At 100 percent, the program passes the examples and at least six extra inputs that you designed. The extra inputs include the smallest case with one talk, a case where all talks start at the same time, a case where talks touch at their ends, a case where two jobs share a deadline and profit, a case where a deadline is larger than m, and a case with zero setup jobs. Each rule is justified with an argument from lesson 4, either an exchange argument or a counterexample check. The code uses clear names and has no unused variables. The whole-program complexity is stated as O(n log n) with a short explanation of which step dominates.

Hints

Try to solve each part yourself before you open a hint. Each hint below is hidden, so you can open one at a time.

Reference solution

This is one complete solution. Try the assignment before you read it, because the goal is to understand each rule, not to copy the code. The reference compiles with g++ -std=c++17 and prints the three lines for all three examples.

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
 
struct Talk {
    int start;
    int finish;
};
 
struct Job {
    int deadline;
    int profit;
};
 
// Part 1: most talks on the stage (earliest finish first).
int stageTalks(vector<Talk> talks) {
    sort(talks.begin(), talks.end(), [](const Talk& a, const Talk& b) {
        return a.finish < b.finish;
    });
    int lastFinish = -1, count = 0;
    for (const Talk& t : talks) {
        if (t.start >= lastFinish) {
            lastFinish = t.finish;
            count++;
        }
    }
    return count;
}
 
// Part 2: fewest rooms. Sweep the start and end events in time order.
int roomsNeeded(const vector<Talk>& talks) {
    vector<pair<int, int>> events;
    for (const Talk& t : talks) {
        events.push_back({t.start, +1});
        events.push_back({t.finish, -1});
    }
    sort(events.begin(), events.end());  // at equal times, an end (-1) comes first
    int rooms = 0, best = 0;
    for (const auto& ev : events) {
        rooms += ev.second;
        best = max(best, rooms);
    }
    return best;
}
 
// Part 3: most profit from setup jobs with deadlines (one job per hour, latest free slot).
long long setupProfit(vector<Job> jobs) {
    int n = (int)jobs.size();
    sort(jobs.begin(), jobs.end(), [](const Job& a, const Job& b) {
        return a.profit > b.profit;
    });
    vector<bool> used(n + 1, false);
    long long total = 0;
    for (const Job& j : jobs) {
        for (int t = min(n, j.deadline); t >= 1; t--) {
            if (!used[t]) {
                used[t] = true;
                total += j.profit;
                break;
            }
        }
    }
    return total;
}
 
int main() {
    int n;
    cin >> n;
    vector<Talk> talks(n);
    for (Talk& t : talks) {
        cin >> t.start >> t.finish;
    }
    int m;
    cin >> m;
    vector<Job> jobs(m);
    for (Job& j : jobs) {
        cin >> j.deadline >> j.profit;
    }
 
    cout << "stage talks: " << stageTalks(talks) << "\n";
    cout << "rooms needed: " << roomsNeeded(talks) << "\n";
    cout << "setup profit: " << setupProfit(jobs) << "\n";
    return 0;
}

The reference has three functions, one for each part, and main only reads the input and prints. This structure is what a reviewer wants to see. Each function can be read and tested alone, and each one states its rule in a comment.

Explaining your solution

When you submit, write a short note of four or five sentences for each part. Name the rule, say why it is correct, and give the complexity. A reviewer should be able to check your reasoning without reading the code.

For Part 1, say that you sort by finish time and why that leaves the most room. Refer to the exchange argument from lesson 4 in one sentence.

For Part 2, say that the number of rooms equals the largest overlap, and explain the tie rule in one sentence. A reviewer should see that you know why an end must come before a start at the same time.

For Part 3, say that you sort by profit and place each job in the latest free hour, and why the latest hour is the right choice. Use the example of a job with deadline 2 and a job with deadline 1 to make the point.

For the whole program, say that the sorts cost O(n log n) and dominate. Part 3 costs O(m squared) in the simple search, which is fine because m is at most 2000. Say that the simple search can be replaced by a disjoint-set structure if m were much larger.

Common mistakes in this assignment

Using one lastFinish for both talks and jobs. Each part has its own rule and its own state. Keep them separate.

Reading the input twice. A second read continues from where the first one stopped, so the second read sees the job numbers, not the talks. The fix is to read the talks once and keep them.

Forgetting that Part 2 needs a tie rule. Without the end-before-start order, Example A gives 3 rooms instead of 2. Check your answer on Example A before you move on.

Capping the job search at n when there are no jobs. If m is 0, the vector of jobs is empty and the used array has one entry. The search loop does not run, and the total is 0. Make sure the code does not index an empty vector.

Printing the wrong words. The three lines must match the format exactly. A judge will count a missing colon as wrong.

Extension, for those who want more

If you finish the three parts early, extend the program in one of these ways. Each one uses ideas from the module.

First, print the actual talks chosen for the stage, in time order. Keep the index of each talk in the struct, then sort the chosen talks by start time before printing.

Second, add a fourth setup rule: the team can spend a fixed budget on setup jobs, and each job costs something. This is not greedy in general. Explain in writing whether the greedy profit rule still works, and give a counterexample if it does not.

Third, replace the simple job search with a faster structure, and measure the difference on 2000 random jobs. Explain what changes and what does not.

Summary

• Activity selection sorts by finish time and takes each talk that starts at or after the last finish.
• The fewest rooms equals the largest number of talks running at the same moment, found with a sorted sweep of start and end events.
• Job sequencing sorts by profit and places each job in the latest free hour at or before its deadline.
• Each part is one greedy rule with one proof idea, and the whole program is O(n log n) because the sorts dominate.
• A good solution tests the examples, invents its own edge cases, and explains each rule in plain words.