Editorial for Faulty Check-in

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Hints

Hint 1
Show Hint At any point in time, Jackson only has 3 options: Check in the first queue student, check in the second queue student, or move the first queue student to the front of the second queue.
Hint 2
Show Hint Because of the first hint, and because we always know the next student Jackson needs to check in, there is always really only a single choice for Jackson - what should Jackson do in what scenario?
Hint 3
Answer to Previous Hint If Jackson sees the next student ID at the front of either queue, he should check them in, always.

Otherwise, he can only take the student in the first queue, and move them to the front of the second queue.
Show Hint Jackson's second queue is not a queue. What is it?

Solution

View Solution Jackson's second queue is not a queue - it's a stack! We always place students and check them in from the front. As was covered in Hint 2, there is only one option Jackson has available at any point in time, so we just need to simulate this second queue current state using a stack, as we read through the input queue.

Comments

There are no comments at the moment.