Rutgers ECE 434 LINUX OS Processes and Inter Process Communication
Question 1 (100 marks total)
You are in charge of managing bookings for car ferries.
There are m car ferries that are numbered from 0 to m 1, in order of their departure time. For simplicity,
no two ferries depart at the same time, and so the numbering is unique. For j in the range 0 to m 1, the
jth ferry to depart is fj whole meters in length. The length of each ferry is non-negative (i.e. it is greater
than or equal to zero).
There are n different cars, c0, c1; : : : cn 1, where n > 0. Each car has a length (in whole meters), as well
as a ferry that they have booked a ticket for. The length of each car must be greater than zero, and the
number of the ferry that they are booked for must be greater than or equal to 0 and less than m 1 (i.e.
no cars can be booked for the last ferry to depart, ferry number m 1).
The cars are ordered in non-decreasing order of the ferry that each car has a ticket for. That is, for any i
from 0 to n 2, the number of the ferry that ci has a ticket booked for is less than or equal to the number
of the ferry that car ci+1 has a ticket booked for.
Each of the first m 1 car ferries may have zero or more car bookings (and the last car ferry can have no
car bookings). In fact, it is possible for one or more of the ferries to be over-booked. A ferry is over-booked
if the sum of the lengths of the cars which are booked for the ferry exceeds the length of the ferry.
Your job, as the manager of the ferry bookings, is to review the bookings and determine a ferry allocation
for each car, where each car is either able to be allocated to:
(i) the ferry that they have a ticket for (their chosen ferry)
(ii) the first ferry that departs after the ferry that they have a ticket for (i.e. if a car has a ticket booked
for ferry j, then they can be allocated to the next ferry, ferry j + 1.)
(iii) no ferry at all { i.e. they can have their ticket canceled.
Such an allocation of cars to ferries is valid if and only if:
There is exactly one allocation for each car, and each car is either allocated to (i) the ferry that they
have a ticket for, or (ii) the first ferry that departs after the ferry that they have a ticket booked for,
or (iii) for no ferry at all.
The sum of the lengths of the cars allocated to each ferry does not exceed (i.e. is less than or equal
to) the length of the ferry.
Note that even though the last ferry cannot have any bookings made for it, cars can still be allocated to it,
i.e. a car with a booking for ferry m 2 may be able to be allocated to ferry m 1.
Each car has as a cost associated with being rescheduled to the next ferry, and a cost associated with having
their ferry ticket canceled. The rescheduling cost, as well as the cancellation cost must be greater than zero,
and the cancellation cost must be greater than the cost of being rescheduled to the next ferry.
The cost of an allocation for a car is either: (i) equal to 0, if the car is allocated to the ferry that they have
a booking for; or (ii) the rescheduling cost for that car, if the car is rescheduled to the next ferry; or (iii)
the cancellation cost for that car, if the car is not allocated to a ferry at all.
Your job is to find a valid allocation of cars to ferries, that minimizes the total allocation cost,
i.e. the sum of the allocation cost for each car.