1

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

OliRod13
  • 21
  • 4
  • Can you formalize the quantity you're trying to optimize? It's not clear why, in your first example, 16:00 (1 hour difference for each) would be better than 15:00 (2 hour difference for one, but 0 difference for the other). – Sneftel May 03 '22 at 10:09
  • @Sneftel, you're right, I will modify the example, I'm sorry. The hardest thing for me is how to do this in the 3rd example. – OliRod13 May 03 '22 at 10:12
  • @RefugnicEternium The issue is the interpretation of "round-the-corner" values. Your suggestion would lead to wrong answers, without actually solving anything. – Sneftel May 03 '22 at 10:18
  • In this case, the next day. That's right, that's the issue. For example, in case "23:00" and "01:00", 23:00 is previous day, and 01:00 is the next, but in "12:00" and "01:00", those are the same days – OliRod13 May 03 '22 at 10:20
  • You could probably do multiple passes on the condition of 'at least one value' being < 12:00 and another value being > 12:00. On the first pass, determine the largest difference like you would for 'same day'. On the second pass, assume '< 12:00' + 24 h and do it again. Use the smaller difference. – Refugnic Eternium May 03 '22 at 10:22

2 Answers2

3

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)
Gassa
  • 8,546
  • 3
  • 29
  • 49
2

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.

Sneftel
  • 40,271
  • 12
  • 71
  • 104