Three people work in a barber shop, but there is space for a fourth. They ask for your help so that they can decide whether to hire another barber. They rent a device that records the time when someone comes to the door of the shop, using a string in the form "HH:MM". Your job is to write a program to analyse these data. (By the way, these devices really exist. See, e.g., FootfallCam.)
For this problem, assume that it takes exactly 15 minutes for each haircut. Also assume that if four people are waiting, anyone else who arrives will leave rather than wait.
The shop opens at 08:00 and closes at 16:00, and only one customer can arrive in any given minute. The barbers want to know the following:
Write a program that reads the file "barber.txt" containing the arrival times (in ascending order) of potential customers to the shop. Analyse the data and output the required information to the console with appropriate labels. For example, you might output:
Longest wait time: 14
Customers lost: 3
Assume that customers who arrive just before closing time receive a haircut, even if the barbers must work past 16:00. (This problem is adapted from the USACO training site, and that's the custom in the USA.) Closing time means that no new customers arrive at 16:00 or later.
If you have to look up how the time library for your chosen programming language works, try not to use it. (For fluency.)
Here is a replit in C++, and this replit is for Python.
I found it useful to use a queue for this problem. A queue is a data structure that provides FIFO (first in, first out) functionality, and it comes up often in programming. Another common data structure is the stack, which provides LIFO (last in, first out) functionality. There are lots of specialised structures built on top of queues and stacks, such as the priority queue and the deque ("deck"). You should familiarise yourself with the native support your programming language provides for these structures. ( Here is a discussion for Python, for example.)
At this point, your programming is quite advanced, so you should be turning your attention to choosing the best algorithm for a particular problem. For this challenge, you could choose to process each customer as he arrives or you could choose to process each minute of the work day. The second approach is simpler, but is it practical? We can calculate 8 hours times 60 minutes (and perhaps ~30 minutes extra to finish the late arrivals), to arrive at roughly 500 iterations. I would choose the second, simpler option in this case because 500 iterations is a perfectly manageable number.
Make sure to do this kind of check on each problem. Some Olympiad tasks may have an "obvious" solution, but it requires billions or even trillions of iterations. In those cases, you will have to find a more clever (and likely more complicated) solution.
You can use this file, which should have a maximum wait of 21 minutes and 9 lost customers.
You can use this file, which should have a maximum wait of 23 minutes and 16 lost customers.