An elevator with a capacity of N people in a building with E floors works in a pretty unusual way.

The elevator starts at the first floor and it goes to the top floor before returning to the first floor.

It stops at every floor that is a destination of a person in the elevator.

It also stops when 1) there is someone at the current floor who wants to travel in the same direction as the elevator is currently traveling and 2) there is still room in the elevator.

At least how many round trips to the top and back are necessary to carry every person to their destination?

I assume that some kind of Greedy algorithm can give a good algorithm to solve this problem, but I still have no idea how to write a pseudocode for it.

  • 2
    $\begingroup$ Welcome to CS.SE! What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. What greedy strategies have you tried so far? Have you tried brainstorming as many greedy approaches as you can and then using the techniques in cs.stackexchange.com/q/59964/755 to see if any of them are correct? $\endgroup$ – D.W. Nov 5 '16 at 20:41
  • 2
    $\begingroup$ I can't understand what the exact algorithmic problem is. What are the inputs? What is the desired output? What do you mean by "every people"? Are you given information about where each person gets on and where they get off, or are you trying to ask about the the worst-case combination of people? Community votes, please: is it clear/unclear what this is asking? $\endgroup$ – D.W. Nov 6 '16 at 18:35
  • $\begingroup$ Haw many is every person? $\endgroup$ – paparazzo Jan 5 '17 at 23:23

I don't see any optimisation problem, no need for any greedy algorithm, nothing.

You described the behaviour of the elevator. All you need to do is to simulate that behaviour and count the number of movements.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.