It is the maximum number of overlapping flights. Sort the all the times in a single array, increment a counter when a plane lands, decrement when it flies.
The other algorithm I think can be by assigning the maximum number of flights to different ladders until all flights are assigned. To assign a ladder maximum number of flights, sort with respect to fly times (finish), assign the first compatible flight (not lands before last assigned flight flies). After processing all the flights if there are more unassigned flights, than you add a ladder and repeat the process. Both algorithms are linear, but if you also need a ladder assignment this might work for you. On Oct 1, 2:48 pm, Dave <dave_and_da...@juno.com> wrote: > 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 <macatad...@gmail.com> 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 <wangyanadam1...@gmail.com> 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 <macatad...@gmail.com> 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 algoge...@googlegroups.com. > > > > To unsubscribe from this group, send email to > > > > algogeeks+unsubscr...@googlegroups.com<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 algoge...@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com<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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
