### 题目

Given a list of 24-hour clock time points in “Hour:Minutes” format, find the minimum minutes difference between any two time points in the list.

Example 1:

Input: ["23:59","00:00"]
Output: 1


Note:

• The number of time points in the given list is at least 2 and won’t exceed 20000.
• The input time is legal and ranges from 00:00 to 23:59.

### 问题分析

• 相同时间戳，比如[00:00, 00:00]间隔视为0.
• 时间戳的顺序不重要，[00:00, 23:59]等价于[23:59, 00:00]，时间间隔都为1.

### 类似“声呐”两头搜索

 -----------------|<----------------    向后搜索
[..., ..., ..., 05:31, ..., ..., ...]
---------------->|-----------------    向前搜索


 -----------------|           |<------  向后搜索
[..., ..., ..., 05:31, ..., 22:08, ...]
|---------->|         向前搜索


#### 代码

class Solution {
private static final int SIZE = 1440;
private static final int HALF = 719;

public int findMinDifference(List<String> timePoints) {
boolean[] timeTable = new boolean[SIZE];
for (String s : timePoints) {
int time = timeToInt(s);
if (timeTable[time]) return 0;
timeTable[time] = true;
}
int minGap = Integer.MAX_VALUE;
for (int i = 0; i < SIZE; i++) {
if (timeTable[i]) {
int forward = (i + 1) % SIZE;
int backward = (i - 1);
if (backward < 0) backward += SIZE;
int gap = 1;
while (gap < minGap && !timeTable[forward] && !timeTable[backward]) {
forward++; backward--;
if (forward >= SIZE) forward %= forward;
if (backward < 0) backward += SIZE;
gap++;
}
minGap = Math.min(minGap, gap);
}
}
return minGap;
}

private int timeToInt(String time) {
int hour = Integer.parseInt(time.substring(0, 2));
int min = Integer.parseInt(time.substring(3, 5));
return hour * 60 + min;
}
}


### 直接计算所有时间戳两两之间的间隔

         gap1                   gap2                    gap3
--->|<----------->|<------------------------------->|<-------
["00:35", ..., "05:31", ..., ..., ..., ..., ..., "22:08", ...]


#### 代码

class Solution {
private static final int SIZE = 1440;

public int findMinDifference(List<String> timePoints) {
boolean[] timeTable = new boolean[SIZE];
for (String s : timePoints) {
int time = timeToInt(s);
if (timeTable[time]) return 0;
timeTable[time] = true;
}
int first = Integer.MAX_VALUE, last = Integer.MIN_VALUE;
int minGap = Integer.MAX_VALUE;
int pre = 0;
for (int i = 0; i < SIZE; i++) {
if (timeTable[i]) {
if (first != Integer.MAX_VALUE) minGap = Math.min(minGap, i - pre);
first = Math.min(first, i);
last = Math.max(last, i);
pre = i;
}
}
return Math.min(minGap, SIZE - (last - first));
}

private int timeToInt(String time) {
return Integer.parseInt(time.substring(0, 2)) * 60 + Integer.parseInt(time.substring(3, 5));
}
}