The bus stop interval is at least T minutes. There is a table of the time of appearance of passengers at the bus stop. How to determine (create an algorithm or write a program) what time should the bus come to a stop, so that the total and the longest waiting time for the bus by passengers is minimal?

  • 2
    Why should he not ride cyclically at intervals of a second? I don’t see any contradictions ... - user8176
  • 2
    ahaha, you still close this question =) - Specter
  • one
    With electric trains easier. Each passenger watches the schedule in advance, comes to the train on time. Bus schedules are a myth. - Yura Ivanov
  • 2
    Those who are responsible and are interested in many ways are right that the task is incorrect. Whether a mistake, or lack of conditions. 1. The bus is not rubber. It is clear that if INT_MAX passengers arrived at the same time, they are unlikely to get on the bus and leave, some will have to wait for the next one. 2. Loading time. This is from real life. While everyone is sitting down, they will pay for the fare, sending is postponed. There may be a situation that the dispatch will be delayed until the bus is full if the passengers stay at least as often as they enter the bus. 3. And most importantly, buses can not spawn for epsilon (+0). - Yura Ivanov
  • one
    You yourself are regulars: -P Of course, this is a fit. The promised prizes are a bit confusing, so the oldfags prefer to keep quiet. - karmadro4


4 answers 4

Iteratively, I describe one iteration.

Find peaks in the table, sort them by descending number of people. Take, for example, 10 peaks. Because The second optimization parameter, i.e. the longest waiting time is less important than the first (the metro is closed at night, and more trains are allowed during rush hours), then we will optimize it secondarily. Those. discharge these 10 peaks in duration, i.e. let's throw back those that are too close to each other. There will be, say, 5 peaks.

Neither will we post the time of arrival of transport.

We will repeat the whole procedure until we rest on the physical limit of the available buses, or violate the laws of physics (for example, the speed of the bus).

    My solution is as follows. Let there be a certain time interval measured with the arrival of the first passenger, measured from 0. We start recording the arrival of passengers from this time interval. As a result, we get a sequence, increasing. The last number will be the maximum. Obviously, the total time was minimal, then you need to submit as many buses as possible for a given period of time. This can be done as follows. Find the remainder of dividing the maximum number by the number T (time interval). From this very moment it is necessary to start serving buses at intervals of t.

      To ensure that the total and the longest waiting time for a bus by passengers is minimal, it is necessary that the arrival time of the bus coincides with the arrival time of the last passenger at the stop, according to the table. Accordingly, it is necessary to adjust the time of departure of the bus so that he could reach the stop no more than T minutes by the time of the arrival of the last passenger.

        In accordance with the schedule of arrival of passengers, a personal bus arrives after each pass :) Then the interval will be at least any non-negative T and the waiting times will be 0 :) Utopia.

        • I agree, the number of buses is not specified. Yes, and the type of route may be different. After all, there are circular routes ... - gecube