As soon as I read:

Users should be able to put a hold on the seats for five minutes before they make a payment to finalize the booking.

The user should be able to wait if there is a chance that the seats might become available, e.g., when holds by other users expire.

Waiting customers should be serviced in a fair, first come, first serve manner.

I would of immediately asked if we could implement this a different way and would have almost taken this as a test as in: will the candidate give critical feedback to a design he sees as being flawed and/or overcomplicated.

My argument would be: From the clients side, the seats are either booked or they are not. When a client enters checkout, they purchase the tickets, then anyone that had those tickets in their cart are alerted that those tickets have been purchased. Another point from a business side is that people want things/results immediately. The first competitor that comes into action that honors the first to pay method is going to steal our clients.