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 |