You can use a sweep like algorithm for that. 1) you sort the land_time,fly_away time points increasingly in time 2) You initialize a counter representing the number of ladders you need at the current time of the sweep line. 3) You process the sorted time time points, when you encounter a "land_time" point you do counter++ and when it is a "fly_away" counter-- 4) The maximum value the counter has reached is the minimum ladder you need (at the peak time).
Pierre On Oct 1, 12:32 pm, mac adobe <macatad...@gmail.com> wrote: > @ Yang .. can you please share book authors so that i can refer .. . > > Please share some insight also .. it will help me understand it. > > --mac > > > > On Fri, Oct 1, 2010 at 4:01 PM, 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. -- 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.
