Find the best time to change the other times the least-CodePudding

I want to find the best common time to change the other times the least (that the sum of the differences is the lowest possible).

On input, I have the array of times.

On output, there should be the new, common time.

Note that the times can be not ordered and be absolutely different (e.g. 02:00, 02:30 and 03:30)

Example 1

Input: ["01:00", "02:00", "03:00", "04:00", "05:00"]

Output should be 03:00, because it's the best to change 01:00 to 03:00 (2 hours of change), 02:00 to 03:00 (1 hour of change), keep 03:00 the same, 04:00 to 03:00 (1 hour), and 05:00 to 03:00 (2 hours).

Example 2

Input: ["12:00", "13:00", "14:00"]

Output should be 13:00 - change 12:00 to 13:00 (1 hour) and 14:00 to 13:00 (1 hour)

Example 3 (tricky)

Input: ["23:00", "01:00", "02:00"]

Output should be 01:00 - change 23:00 to 01:00 (2 hours) and 02:00 to 01:00 (1 hour) (the tricky thing is 23:00 - the best time is not 13:00)

I tried functions that make the average of times, e.g. https://stackoverflow.com/a/52839039/19022995, but unfortunately it doesn't work

I would be really grateful for tips how to do this

Thank you in advance

CodePudding user response：

Lemma: an optimal answer coincides with one of the given times.

To prove it, consider a solution that doesn't coincide with any of the given times. Try to move it a bit forward and then a bit backward. In at least one of the cases, the total difference does not increase. So, continue moving in that direction until you hit one of the given times.

What is left now is to write a function that computes the difference, taking wraparound from 23:59 to 00:00 into account.

After that, try every given time as a candidate answer, calculate the total difference for each, and pick the best one as the final answer.

In pseudocode:

time (h, m) = h * 60   m

diff (t1, t2) = min (abs (t1 - t2), 60 * 24 - abs (t1 - t2))

t[0..n) = given times

total (x) = sum {diff (x, t[i])} for i in [0..n)

answer = arg min {total (t[i])} for i in [0..n)

CodePudding user response：

One approach is to look for the smallest "window" containing all the times. To do this, sort the times (naively) and, consider each time as being the "first". For instance, in your third example, considering 1:00 as the first time would lead to a 22 hour window (because that makes the "last" time 23:00); considering 2:00 as the first time would lead to a 23 hour window; but considering 23:00 as the first time would lead to a 3 hour window. From there, simply calculate relative to that first time, calculating differences mod 24.