题目描述

给定一个 24 小时制（小时:分钟）的时间列表，找出列表中任意两个时间的最小时间差并已分钟数表示。

样例

输入: ["23:59","00:00"]
输出: 1

注意

• 列表大小在 2~20000 之间。
• 每个时间取值在 00:00~23:59 之间。

算法

(排序) $O(n \log n)$

1. 将原数组按照小时，分钟从小到大排序。
2. 排序后，末尾再添加一个时间为最早的时间加24小时。
3. 然后从第二个时间开始和前一个时间对比找最小值即可。

时间复杂度

• 排序后，仅需要线性扫描，故时间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    int findMinDifference(vector<string>& timePoints) {
        int n = timePoints.size();
        vector<pair<int, int>> times;
        for (string s : timePoints)
            times.push_back(make_pair(stoi(s.substr(0, 2)), stoi(s.substr(3, 2))));

        sort(times.begin(), times.end());
        times.push_back(make_pair(times[0].first + 24, times[0].second));

        int ans = 10000;
        for (int i = 1; i <= n; i++) {
            int h = times[i].first - times[i - 1].first;
            int m = times[i].second - times[i - 1].second;
            ans = min(ans, h * 60 + m);
        }
        return ans;
    }
};