[LeetCode] Minimum Time Difference

发表于 | 更新于: | 分类于 |

题目描述

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.
输入是一个时间的数组，要求求出最小的时间间隔。思路是对时间排序，然后求每相邻两个时间间隔的时间差与第一个时间与最后一个时间的时间差。比较得到最小的时间间隔。

C++ 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public:
    int findMinDifference(vector<string>& timePoints) {
        struct Time
        {
            uint8_t hour;
            uint8_t min;
            Time(const uint8_t hour, const uint8_t min)
                : hour(hour), min(min)
            {
            }

            bool operator<(const Time& other) const
            {
                if (hour < other.hour)
                {
                    return true;
                }
                else if (hour == other.hour)
                {
                    return min < other.min;
                }
                return false;
            }

            int operator-(const Time& other) const
            {
                int hour_diff = hour - other.hour;
                int min_diff = min - other.min;

                return hour_diff * 60 + min_diff;
            }
        };

        vector<Time> times;
        times.reserve(timePoints.size());
        for (const string& time_point : timePoints)
        {
            const size_t idx = time_point.find(":");
            const uint8_t hour = stoi(time_point.substr(0,idx));
            const uint8_t min = stoi(time_point.substr(idx + 1,time_point.size() - idx));
            times.emplace_back(Time{hour,min});
        }

        sort(times.begin(), times.end());

        int res = INT_MAX;
        for (int i = 0; i < times.size() - 1; i++)
        {
            const Time& t1 = times[i];
            const Time& t2 = times[i + 1];
            res = min(t2 - t1, res);
        }

        const Time first_t(times.front().hour + 24, times.front().min);
        const Time& last_t = times.back();
        res = min(first_t - last_t, res);

        return res;
    }
};
Donate
0%