| CS19002 Programming and Data Structures Laboratory | Spring 2010, Section 5 |
Suppose that you are the owner of a car rental company. You are given a set of requests for the next month. Each request has a start date and a finish date, and requires a car from the start date to the finish date (both inclusive). Suppose that the days of the next month are numbered 1,2,...,30, and each request occupies a car for a whole number of days. A random way of generating a schedule of n requests is given in the following function which stores the start and finish times in two separate arrays.
#define NDAYS 30
#define LONGEST 10
void genReq ( int start[], int finish[], int n )
{
int i, s, f;
srand((unsigned int)time(NULL));
i = 0;
while (i < n) {
s = 1 + rand() % NDAYS;
f = s + rand() % LONGEST;
if (f <= NDAYS) {
start[i] = s;
finish[i] = f;
++i;
}
}
}
Sort the requests in the increasing order of start date. Use any sorting algorithm of your choice. Whenever you swap two elements of the start[] array, you should also swap the elements at the same locations in the finish[] array. Write a function to do this sorting. The function should have the following prototype:
void sortReq ( int start[], int finish[], int n );
The requests will be numbered 0 through n-1 after sorting.
Prepare an array next[] such that next[i] stores the first request that can be served after the completion of the i-th request. A car cannot serve two (or more) requests on the same day. So next[i] is the request j with j as small as possible such that start[j] > finish[i]. If no such j exists, take next[i] = n. Write a function with the following prototype:
void getNext ( int start[], int finish[], int next[], int n );
After the next[] array is generated, print the requests using the following function.
void printReq ( int start[], int finish[], int next[], int n )
{
int i;
for (i=0; i<n; ++i)
printf("Request %2d: %2d -- %2d (%2d)\n", i, start[i], finish[i], next[i]);
}
Write a function with the prototype
void genSchedule ( int start[], int finish[], int next[], int n );
in order to generate a schedule of requests that you are going to serve by a single car. Your goal is to maximize the utilization of the car, that is, you want to keep the car engaged for as many days as possible in the next month. In order to generate this best schedule, proceed as follows.
Use two arrays serve[] and best[]. The element best[i] stores the best utilization of your car for the requests i through n-1. Of course, you are interested in best[0], but the determination of this requires the values best[i] for i >= 1. Let us see how we can compute best[i].
If you serve the i-th request, you cannot serve the requests j with i < j < next[i], because a car cannot serve two (or more) requests on the same day. Therefore, the best possible utilization of your car in this case is u1 = (finish[i] - start[i] + 1) + best[next[i]].
On the other hand, if you do not serve request i, your best utilization of the car is u2 = best[i+1].
Depending upon which one of u1 and u2 is larger, populate the array entries best[i] and serve[i]. Be very careful about the order of i in which these arrays are to be populated.
When the two arrays best[] and serve[] are fully populated, print the requests that are going to be served, using the information computed and stored in these arrays. Also print the total utilization of your car for serving the requests according to your schedule.
Use the following main() function. YOUR PROGRAM MUST NOT USE ANY GLOBAL VARIABLES OR ARRAYS. Pass all arrays as parameters. You must learn how to do that.
#define NREQ 25
int main ()
{
int start[NREQ], finish[NREQ], next[NREQ];
genReq(start,finish,NREQ);
sortReq(start,finish,NREQ);
getNext(start,finish,next,NREQ);
printReq(start,finish,next,NREQ);
genSchedule(start,finish, next,NREQ);
exit(0);
}
An output for 15 requests is shown below. (You are supposed to report your output for 25 requests.)
Request 0: 5 -- 8 ( 6) Request 1: 5 -- 7 ( 5) Request 2: 5 -- 5 ( 3) Request 3: 6 -- 9 ( 6) Request 4: 7 -- 16 (11) Request 5: 8 -- 11 ( 8) Request 6: 10 -- 13 ( 8) Request 7: 10 -- 18 (12) Request 8: 14 -- 23 (14) Request 9: 15 -- 16 (11) Request 10: 15 -- 17 (12) Request 11: 17 -- 23 (14) Request 12: 21 -- 27 (15) Request 13: 22 -- 23 (14) Request 14: 27 -- 27 (15) Recommended schedule: 2 3 7 12 Total utilization: 21
| Lab Home | Submission Site | My Home |