PeripateticShippingLines,Inc.,isashipping company that owns nships and provides service to n ports. Each of its ships has aschedule that says, for each day of the month, which of the portsit’s currently visiting, or whether it’s out at sea. (You canassume the “month” here has m days, for some m > n.) Each shipvisits each port for exactly one day during the month. For safetyreasons, PSL Inc. has the following strict requirement:

(†) No two ships can be in the same port on the same day.

The company wants to perform maintenance on all the ships thismonth, via the following scheme. They want to truncate each ship’sschedule: for each ship Si, there will be some day when it arrivesin its scheduled port and simply remains there for the rest of themonth (for maintenance). This means that Si will not visit theremaining ports on its schedule (if any) that month, but this isokay. So the truncation ofSi’s schedule will simply consist of itsoriginal schedule up to a certain specified day on which it is in aport P; the remainder of the truncated schedule simply has itremain in port P.

Now the company’s question to you is the following: Given thesched- ule for each ship, find a truncation of each so thatcondition (†) continues to hold: no two ships are ever in the sameport on the same day.

Show that such a set of truncations can always be found, andgive an algorithm to find them.

Example. Suppose we have two ships and two ports, and the“month” has four days. Suppose the first ship’s schedule is

port P1; at sea; port P2; at seaand the second ship’s scheduleisat sea; port P1; at sea; port P2

Then the (only) way to choose truncations would be to have thefirst ship remain in port P2 starting on day 3, and have the secondship remain in port P1 starting on day 2.