You need to move from one arrival-or-departure-time to another in
order throughout the day. An arrival means that another ladder is put
into use, while a departure takes a ladder out of use. Here is an
efficient algorithm to do that:
Form a min-heap of the arrival times. Include the departure time and a
flag in the heap as to whether the heap condition is based on the
arrival time or a departure time. (See below)
Set number_of_ladders_in_use = 0, number_of_ladders_required = 0.
Loop until the heap is empty:
Look at the top heap item.
If it is an arrival time:
Increment number_of_ladders_in_use.
number_of_ladders_required = max(number_of_ladders_required,
number_of_ladders_in_use).
Replace the arrival time by the departure time and set the
flag accordingly.
Restore the min-heap condition (see below).
Else // it is a departure time
Decrement number_of_ladders_in_use.
Delete the top entry in the min-heap.
Restore the min-heap condition (see below).
When the heap is empty, number_of_ladders_required is the minimum
number of ladders required.
Note: When restoring the min-heap condition, break ties between
identical arrival and departure times based on whether the ladder can
be moved instantly from one plane to another. E.g., if a plane departs
at noon and another arrives at noon, put the departure first in the
heap if the same ladder can be used for both, but put the arrival
first if it takes time to move the ladder from one plane to another,
in which case the same ladder cannot be used.
Dave
On Oct 1, 5:31 am, mac adobe <[email protected]> wrote:
> correcting ... Its minimum numbers of ladders required
>
> Please suggest how you think for this problem
> Suppose you have many airplanes . Each plane needs a ladder so
> that people can board the plane easily .
> Now plane will land at time land_time and then fly away again at fly_time .
> During this time , people will continue to board the plane and the
> ladder should remain attached to the plane. So if plane lands at 3 am and
> fly at 3 pm , we need a ladder from 3 am to 3 pm dedicated for that plane.
> Given land_time and fly_time of multiple planes in a day , find the
> minimum
> number of ladders your require .
>
> --mac
>
>
>
> On Fri, Oct 1, 2010 at 3:56 PM, Yan Wang <[email protected]> wrote:
> > I think your question should be to find the minimum number of ladders
> > required.
>
> > This is a very classic Greedy-Algorithm solved problem. Please refer
> > to Chapter 4 of book "Algorithm Design".
>
> > On Fri, Oct 1, 2010 at 2:32 AM, mac adobe <[email protected]> wrote:
> > > Hi
> > > Please suggest how you think for this problem
> > > Suppose you have many airplanes . Each plane needs a ladder so
> > > that people can board the plane easily .
> > > Now plane will land at time land_time and then fly away again at fly_time
> > .
> > > During this time , people will continue to board the plane and the
> > > ladder should remain attached to the plane. So if plane lands at 3 am and
> > > fly at 3 pm , we need a ladder from 3 am to 3 pm dedicated for that
> > plane.
> > > Given land_time and fly_time of multiple planes in a day , find the
> > minimum
> > > number of ladders your require .
>
> > > --mac
>
> > > --
> > > You received this message because you are subscribed to the Google Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to [email protected].
> > > To unsubscribe from this group, send email to
> > > [email protected]<algogeeks%2bunsubscr...@googlegroups.com>
> > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to [email protected].
> > To unsubscribe from this group, send email to
> > [email protected]<algogeeks%2bunsubscr...@googlegroups.com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
>
> - Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
