CS 14 - Lab 10

Create a method to solve the activity selection problem.

The Method

The method should take 3 parameters: an array s that contains the starting times of the proposed activities, an array f that contains the ending times, and the size of the arrays. (Note: the arrays should be of type int.) The method should return a dynamically allocated array that contains the indices of the activities that can be scheduled.

The method should first sort the arrays by ending times. Create a separate method to do this. You can use any sorting method you like (bubblesort, quicksort, etc.). The easiest thing to do is to modify one of the sorting methods you wrote earlier in the quarter. (It must be modified because you will need to pass it 2 arrays, not just 1.)

Once the arrays are sorted, dynamically create an array in which to return the indices. Make it the size of the input arrays + 1.

Determine which activies can be scheduled, using the activity selection algorithm given in the book and in lecture. As an activity is scheduled, add it to the array. After all of the activities have been scheduled, "terminate" the array with -1.

For example, say there are 10 potential activities to schedule. You would create a return array of size 11. Say two activities, numbers 3 and 5, can be scheduled. The return array would return 3 values: 3, 5, and -1. The rest of the array will simply not be filled.

Main

Create a main program that asks the user to input a series of starting and ending times for activities, up to 15 activities. You do not need to validate the input (such as making sure each ending time is larger than the starting time). Once the activities are entered, call the activity selection method, then print out the results from returned array. (Do not print the -1 at the end of the array.) Finally, delete the return array.

Following is a sample run:

This program will solve an instance of the activity selection problem.

Enter start  time for activity 1 (-1 to stop): 2
Enter ending time for activity 1             : 5

Enter start  time for activity 2 (-1 to stop): 4
Enter ending time for activity 2             : 6

Enter start  time for activity 3 (-1 to stop): 1
Enter ending time for activity 3             : 4

Enter start  time for activity 4 (-1 to stop): -1


The following activities can be scheduled: 3 2

Grading

When you have finished the program, your TA will grade it. To receive full credit, your TA will check all of the following:

The program works correctly
The program is properly commented. The function should have a comment at the beginning explaining what it does, what each of its parameters are for, and the return value.
The program is well formatted (i.e. style). For example, you should be consistent with your indenting in the program.

Lab Grades For the Quarter

At the end of this week, the TA will be submitting your lab grades for the quarter. Therefore, you should verify that your TA has all of your scores and that they are correct. Any discrepencies should be dealt with by you and the TA prior to the TA submitting the lab grades.