implementing a simple elevator algorithm

Question

I want to implement a simple elevator algorithm.

People on different floors orders the elevator and the destination floor they want to get to (so you get a {from, to} alert from different floors).

So I got a simple strightforward solution:

Once the elevator starts going in a specific direction (let's say up) it will continue doing so, and serve all request of people wanting to go up (only if at the time they were made they were from higher floor in respect to the elevator) until serving the last one. All the requests will be kept in an array, so on each floor you can check if someone wants to go on the same current direction.

In addition I'll save in two vars (on for up direction and one for down direction) the highest and lowest points of request - highest floor that somebody wants to go up from there, and lowest floor that somebody wants to get to lower floors from there - and the elevator always will be travling between these two points picking all the people that want to go on the same direction.

Does this solution make sense/work?
Is there something as simple that makes more sense?

I saw some priority queue suggestions while searching in google but didn't really understand what the need of them ..

• Auberon: Priority queues are used when you want your elevator to serve the passenger whose floor is the closest to the current one first.
• Rick Decker: Did you do any research? There's been a lot of work done in this area over the years. IIRC, Knuth took time off to study exactly this topic.
• greybeard: One thing to consider would be elevator capacity. Timing gets interesting if not only time to enter/leave depends on occupancy, but also movement (in persons, if not in kilograms). Also, consider one person going up to some floor $f-1,ドル and one down from $f$ to $f-1$: shall the elevator stop at $f-1$ twice? (How about serving odd floors going up, and even floors going down? (More reasonable with complementary elevators side by side.) (Does floor 13 exist?)) I wonder what they are using in the vertical ghettos of, say, Hong Kong. (Please use a spelling checker and correct the title, too.)
• gnasher729: @greybeard Skipping floors is an excellent idea. This could be a time saver. It could be psychologically difficult because the person whose floor was skipped at first may be annoyed.

Answer 1

Of course your approach will work but the answer to your question: "Does this solution make sense?" is entirely dependent on the situation.

Priority Queues are used (e.g.) when you want to serve the passenger whoever's destination floor is closest to the current one. Said passenger will have very high priority. This has a disadvantage that when a passenger wants to go to a floor that is far away from the current one, he will be assigned a very low priority and will be served never/late. This can be solved by increasing the priority for a passenger over time.

Your approach has the advantage that there's a maximum waiting time known for all passengers. That is, the time it takes for a person to go to floor 1 when he gets in at floor 2 while the elevator is going up all the way to the penthouse and it stops at all floors along the way. The advantage of knowing this isn't present in the case (or it is at least not easy) in the priority queue approach. But you can imagine that the situation described can be very annoying for the involved passenger since he will have to travel along the full building almost twice to lower just one floor.

Another approach I'm thinking of while writing this makes use of priority queues where the priority of going to a floor is the number of people that needs to get in/off at that floor.

In conclusion, I think the advantage of your approach isn't very useful and it has a big disadvantage as well. I would look into priority queues and then define for yourself what priority means. Maybe your priority is to deliver groups of people to floors at once (last approach) or maybe it's to deliver the passenger whoever's floor is closest, (first approach). As said before, deciding if an approach is good depends entirely on the situation.

• gnasher729: "Priority queues" are just a clever algorithm to find the smallest item in an array in constant time and remove it or insert a new one in log n time. It doesn't really have anything to do with "priorities". And your numbers are likely so small that log n vs n doesn't make a difference.