Project 1: Activity Scheduling

Due: Tuesday, February 23, 2016 by 9:00PM


An additional test program proj1test.cpp has been posted. Put this file in the same directory as sched.cpp and compile just proj1test.cpp. On GL, just type: g++ proj1test.cpp When you run the program, the output should look like this: proj1test-outupt.txt.

We are releasing this test program because we have noticed that the you are not testing your code even though we have said that you need to test you code. Here's what it means to test your code:

  • Use new data with different sizes.
  • Check that your sort function actually sorts. You should have printed out the events in end time order after sorting and check it either visually or with a short piece of code, preferrably both.
  • After scheduling, check that the output is correct. In this case, the data was arranged so that "Event A", ..., "Event G" are the scheduled events.

This is code you should have written yourself to test your program. We expect you to do this for all the projects.

You should NOT just run this program and say "Great, I'm done!" You should make new data to go into proj1test.cpp to further test your code. If all you do is run proj1test.cpp unmodified, you have once again failed to understand that it is your responsibility to test your own code.

We will not do this again for future projects in this class.


In this project, you will demonstrate your ability to apply basic C/C++ syntax, user-defined functions, and arrays to implement a solution to a room scheduling problem.


Suppose we are in charge of scheduling events in a lecture hall. For any given day, we have a list of event requests, which include the events' start times, end times, and descriptions. Our goal is to schedule as many events as possible. This is known as the activity-selection problem. For example, suppose we have three requests for ITE 102:

It is easy to see that we can schedule at most two events, and that there are two different ways to achieve this:

  1. Spanish 101 and Study Group
  2. Big Cheddar Fussball Camp and Study Group

We only care that we schedule as many events as possible, so either of these two options is acceptable. We will say a schedule is optimal if it includes the maximum number of events. This example shows that there may be multiple optimal solutions.

It turns out that there is an efficient algorithm for finding optimal solutions to the activity-selection problem. Here is an outline of the algorithm:

  1. Sort the events in ascending order by end time.
  2. Schedule the first event on the sorted list; remove the event scheduled and all events that start before the scheduled event ends.
  3. Repeat the previous step until there are no more events to schedule.

We can apply this algorithm to the example given above. First, we sort the events by end time:

We schedule the event Spanish 101 since it has the earliest end time. Next, we remove Spanish 101, Big Cheddar Fussball Camp, and Algorithms Workshop from the list. This leaves only Study Group, which we add to the schedule. Since there are no more event requests, we are done. The resulting schedule is:


Your assignment is to write three functions necessary to complete an activity-scheduling program. The main() function, function prototypes, and one set of test data are provided in two files:

On GL, these files can be copied from Prof. Marron's shared directory: /afs/ You may not modify the provided function prototypes or main() function. You will write the function implementations; they must be written in sched.cpp following the main() function.

The event data is provided in the header file sched.h. You should not modify the data in the provided header file, but you may create other header files to test your program with other event lists. To compile the program using event data in a different header file, you will need to change the line #include "sched.h" in sched.cpp to reference the new header file.

The number of events is given by the constant NUM_EVENTS, and the event data is given in three arrays:

The three functions you must implement are sort(), sched(), and printEvent():

See the function prototypes and comments in sched.cpp for more information.

Implementation Issues

Here are some issues to consider and pitfalls to avoid.

Sample Output

With the data provided in sched.h, your program should schedule five events:

linux2[1]% ./sched 
07:30 - 08:30 Breakfast Club 
10:30 - 12:30 Teaching Workshop 
14:00 - 14:45 Big Cheddar Fussball Camp 
16:00 - 17:00 Delta Tau Chi 
17:00 - 18:00 Dead Poets Society

Submitting your program

You should submit these files to the proj1 subdirectory:

If you followed the directions in setting up shared directories, then you can copy your code to the submission directory with: cp sched.h sched.cpp ~/cs202proj/proj1/

You can check that your program compiles and runs in the proj1 directory, but please clean up any .o and executable files. Again, do not develop your code in this directory and you should not have the only copy of your program here.