PROBLEM STATEMENT
Implement a class that simulates the work of an elevator. Given a list of
requested floors, determine the order of stops an elevator would make.
DEFINITION
Class name: Elevator
Method name: getStops
Parameters: String[]
Return type: String[]
Method signature: String[] getStops(String[] requests) (make sure your method
is public)
Each String is formatted as follows (quotation marks are included for clarity
only)
"time from to"
Each entry contains information about a single request; It has three integer
components separated by spaces - time, from, and to. Time represents the number
of seconds passed from the beginning of the simulation; from is the number of
the floor from which this request comes; to is the number of the destination
floor for this request.
TopCoder will check that
- requests will contain 0 to 25 elements, inclusive
- requests will be ordered by time, with earlier requests placed first
- time will be in the range from 0 to 10000, inclusive; all values will be unique
- Both from and to will be in the range from 0 to 99, inclusive
- Each request will be either to go up or to go down, meaning that the value of
from will not be equal to the value of to for the same request.
Elements of the return value of getStops should be formatted as follows
(quotation marks are included for clarity only)
"time floor"
time and floor are integer values separated by a single space. Entries should
be ordered by time, with earlier stops placed first.
NOTES
* Initially, the elevator is on the ground floor (floor 0).
* It takes the elevator one second to travel one floor, regardless of the
direction.
* When the elevator is moving up, it queues all the requests for going down
until it reaches the highest requested floor; when the elevator is moving down,
it queues all requests for going up until it reaches the lowest requested floor.
* When the elevator receives a request to go up while moving up, it queues all
requests that come from floors lower than the current one, and executes all
requests that come from the current floor and higher.
* Similarly, when the elevator receives a request to go down while moving down,
it queues all requests that come from floors higher than the current one, and
executes all requests that come from the current floor and lower.
* After the elevator has serviced all requests for going up, it will move to
the highest floor of all requests for going down and begin servicing requests
for going down. After the elevator has serviced all requests for going down,
it will move to the lowest floor of all requests for going up and begin
servicing requests for going up.
* When the elevator arrives at a floor at the same time that a request is
received, the request may override the decision to stop at the current floor
and change directions. See example below.
* Once the elevator stops on a requested floor, it opens its doors for five
seconds, and waits; during this time, the elevator queues all requests, but
does not make a decision to reverse its direction (see example 1).
* When the elevator does not have queued requests, it stays on the last
requested floor.
* When the elevator is not moving and its doors are closed, it starts executing
a request the second the request comes in.
* When the elevator is waiting with its doors opened, and a request originating
from the current floor in the direction of current travel arrives, the elevator
restarts its five-second waiting from the moment the request arrived (see
example 3).
EXAMPLES
1. If requests={"0 3 5", "12 4 0", "13 8 9"}, the sequence of events is as
follows:
- Second 0: The elevator starts moving to floor number 3
- Second 3: The elevator reaches floor number 3, and waits for five seconds
- Second 8: The elevator starts moving to floor number 5
- Second 10: The elevator reaches floor number 5, and waits for five seconds
- Second 12: Request to go from 4 to 0 is queued
- Second 13: Request to go from 8 to 9 is queued
- Second 15: The elevator starts moving to floor number 8, even though the
request 4-0 came earlier. This is because the elevator was on its way up before
the last stop.
- Second 18: The elevator reaches floor number 8, and waits for five seconds
- Second 23: The elevator starts moving to floor number 9
- Second 24: The elevator reaches floor number 9, and waits for five seconds
- Second 29: The elevator starts moving to floor number 4
- Second 34: The elevator reaches floor number 4, and waits for five seconds
- Second 39: The elevator starts moving to floor number 0
- Second 43: The elevator reaches floor number 0
Your method should return {"3 3","10 5","18 8","24 9","34 4","43 0"}
2. If requests={"1 1 2", "2 3 0"}, the sequence of events is as follows:
- Second 1: the elevator starts moving to floor number 1
- Second 2: The elevator reaches floor number 1, and waits for five seconds. At
the same time, request to go from 3 to 0 arrives; the elevator queues this
request
- Second 7: The elevator starts moving to floor number 2
- Second 8: The elevator reaches floor number 2, and waits for five seconds
- Second 13: The elevator starts moving to floor number 3
- Second 14: The elevator reaches floor number 3, and waits for five seconds
- Second 19: The elevator starts moving to floor number 0
- Second 22: The elevator reaches floor number 0
Your method should return {"2 1","8 2","14 3","22 0"}
3. If requests={"0 10 20", "13 10 15"}, the sequence of events is as follows:
- Second 0: the elevator starts moving to floor number 10
- Second 10: The elevator reaches floor number 10, and waits for five seconds
- Second 13: A request to go from floor 10 to 15 arrives; the elevator resets
its wait timer back to five seconds
- Second 18: The elevator starts moving to floor number 15
- Second 23: The elevator reaches floor number 15, and waits for five seconds
- Second 28: The elevator starts moving to floor number 20
- Second 33: The elevator reaches floor number 20
Your method should return {"10 10", "23 15", "33 20"}
4. If requests={"0 0 5","5 10 5", "20 15 10"}, the sequence of events is as
follows:
- Second 0: A request to go from floor 0 (the initial floor) to floor number 5
arrives. The elevator waits for five seconds
- Second 5: A request to go from floor 10 to floor 5 arrives. Since the
elevator is moving up, this request is queued. The elevator starts moving to
floor number 5
- Second 10: The elevator reaches floor number 5, and waits for five seconds
- Second 15: The elevator starts moving to floor number 10
- Second 20: A request to go from floor 15 to floor 10 arrives. The elevator
reaches floor number 10. The elevator does not stop, however since the request
from floor 15 overrides this decision.
- Second 25: The elevator reaches floor number 15, and waits for 5 seconds
- Second 30: The elevator starts moving to floor number 10
- Second 35: The elevator reaches floor number 10 and waits for 5 seconds
- Second 40: The elevator starts moving to floor number 5
- Second 45: The elevator reaches floor number 5
Your method should return {"0 0","10 5","25 15","35 10","45 5"}
Note that the first element is "0 0", even though the elevator was on the
ground floor already. Still this is considered a stop, because the elevator
opened its doors.
5. If requests={"0 0 5","5 10 5", "21 15 10"}, the sequence of events is as
follows:
- Second 0: A request to go from floor 0 (the initial floor) to floor number 5
arrives. The elevator waits for five seconds
- Second 5: A request to go from floor 10 to 5 arrives. Since the elevator is
moving up, this request is queued. The elevator starts moving to floor number 5
- Second 10: The elevator reaches floor number 5, and waits for five seconds
- Second 15: The elevator starts moving to floor number 10
- Second 20: The elevator reaches floor number 10, and waits for five seconds
- Second 21: A request to go from floor 15 to floor 10 arrives. Since the
elevator's direction of movement is down, this request is queued
- Second 25: The elevator starts moving to floor number 5
- Second 30: The elevator reaches floor number 5, and waits for five seconds
- Second 35: There are no more requests from lower floors, so the elevator
starts moving to floor 15 to service the last request
- Second 45: The elevator reaches floor number 15, and waits for 5 seconds
- Second 50: The elevator starts moving to floor number 10
- Second 55: The elevator reaches floor number 10
Your method should return {"0 0","10 5","20 10","30 5","45 15","55 10"}
6. If requests={"0 0 99","1 1 99"}, the sequence of events is as follows:
- Second 0: A request to go from floor 0 (the initial floor) to floor number 99
arrives. The elevator waits for five seconds
- Second 1: A request to go from floor 1 to floor 99 arrives
- Second 5: The elevator starts moving to floor number 99
- Second 6: The second reaches floor number 1, and waits for five seconds
- Second 11: The elevator continues moving to floor number 99
- Second 109: The elevator reaches floor number 99
Your method should return {"0 0","6 1","109 99"}
7. If requests={"0 50 40","1 70 60"}, the sequence of events is as follows:
- Second 0: A request to go from floor 50 to floor 40 arrives, the elevator
starts moving to floor 50
- Second 1: A request to go from floor 70 to floor 60 arrives
- Second 50: The elevator passes floor 50 and does not stop since floor 70 is
the highest floor request
- Second 70: The elevator reaches floor number 70, and waits for five seconds
- Second 75: The elevator starts moving to floor number 60
- Second 85: The elevator reaches floor number 60, and waits for five seconds
- Second 90: The elevator starts moving to floor number 50
- Second 100: The elevator reaches floor number 50, and waits for five seconds
- Second 105: The elevator starts moving to floor number 40
- Second 115: The elevator reaches floor number 40
Your method should return {"70 70","85 60","100 50","115 40"}
8. If requests={"0 0 20","16 5 30"}, your method should return {"0 0","25
20","45 5","75 30"}