找出最合适的时间去改变其他时间--最少

Question

我想找到最好的共同时间，以改变其他时间最少(差异的总和是最低的可能)。

在输入时，我有一系列的时间。

在产出方面，应该有新的、共同的时间。

请注意，时间不能被命令和绝对不同(例如: 02:00，02:30和03:30)

示例1

输入：["01:00", "02:00", "03:00", "04:00", "05:00"]

输出应该是03:00，因为更改01:00至03:00 (2小时)、02:00至03:00 (1小时)、03:00保持不变、04:00至03:00 (1小时)和05:00至03:00 (2小时)是最好的。

示例2

输入：["12:00", "13:00", "14:00"]

输出应为13:00 -更改12:00至13:00 (1小时)和14:00至13:00 (1小时)

示例3(棘手)

输入：["23:00", "01:00", "02:00"]

输出应该是01:00 -更改23:00到01:00 (2小时)和02:00到01:00 (1小时)(棘手的事情是23:00 -最佳时间不是 13:00)。

我尝试了一些使平均次数(如https://stackoverflow.com/a/52839039/19022995 )达到平均值的函数，但不幸的是，它无法工作。

我真的很感激你给我的建议

提前谢谢你

Answer 1

引理：最优解与给定时间之一一致。

要证明这一点，请考虑一个与给定时间不一致的解决方案。试着向前移动，然后再向后移动。至少在其中一种情况下，总差额没有增加。所以，继续朝这个方向移动，直到你到达给定的时间之一。

现在剩下的是编写一个计算差异的函数，考虑到23:59到00:00之间的舍入。

在此之后，尝试每一个给定的时间作为候选答案，计算每个时间的总差异，并选择最佳的一个作为最终答案。

伪码：

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)

Answer 2

一种方法是寻找包含所有时间的最小“窗口”。要做到这一点，就得(天真地)对时间进行排序，并将每一次都视为“第一次”。例如，在第三个示例中，将1:00视为第一次将导致22小时窗口(因为这将导致“最后”时间23:00)；将2:00作为第一次时间将导致23小时窗口；但将23:00视为第一次窗口将导致3小时窗口。从那里，简单地计算相对于第一次，计算差异模24。