Given a list of 24-hour clock time points in "Hour:Minutes" format, find the minimumminutesdifference between any two time points in the list.

Example 1:

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

Output: 1

Note:

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

Solution 1: bucket sort, 共24*16个bucket

    public int findMinDifference(List<String> timePoints) {
        boolean[] mark = new boolean[24 * 60];
        for (String cur : timePoints) {
            int hour = (cur.charAt(0) - '0') * 10 + (cur.charAt(1) - '0');
            int minute = (cur.charAt(3) - '0') * 10 + (cur.charAt(4) - '0');
            int index = hour * 60 + minute;
            if (mark[index]) {
                return 0;
            }
            mark[index] = true;
        }
        int prev = Integer.MAX_VALUE, first = 0, last = 0, min = Integer.MAX_VALUE;
        for (int i = 0; i < 24 * 60; i++) {
            if (mark[i]) {
                if (prev != Integer.MAX_VALUE) {
                    min = Math.min(min, i - prev);

                } else {
                    first = i;
                }
                prev = i;
                last = i;
            }
        }
                             //注意最后一个与第一个的case
        return Math.min(min, 24 * 60 - last + first);
    }

Solution 2: sort

public int findMinDifference(List<String> timePoints) {
    Collections.sort(timePoints);
    int minDiff = Integer.MAX_VALUE;
    String prev = timePoints.get(timePoints.size()-1);
    for (String s : timePoints) {
        int prevMins = Integer.parseInt(prev.split(":")[0])*60 + Integer.parseInt(prev.split(":")[1]);
        int curMins = Integer.parseInt(s.split(":")[0])*60 + Integer.parseInt(s.split(":")[1]);
        int diff = curMins - prevMins;
        if (diff < 0) diff += 1440;
        minDiff = Math.min(minDiff, Math.min(diff, 1440 - diff));
        prev = s;
    }
    return minDiff;
}

Solution 3: PQ

public int findMinDifference(List<String> timePoints) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for (String s : timePoints) {
        int h = Integer.valueOf(s.substring(0,2));
        int m = Integer.valueOf(s.substring(3));
        pq.offer(h*60+m);
    }
    if (pq.size() < 2) return 0;
    int res = Integer.MAX_VALUE, first = pq.poll();
    int cur = first;
    while (!pq.isEmpty()) {
        int next = pq.poll();
        res = Math.min(res, next-cur);
        cur = next;
    }
    return Math.min(res, 24*60-cur+first);
}