539. Minimum Time Difference

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

• new solution update 2022.05.13

class Solution {
    int toTime(string& timePoint) {
        auto pos = timePoint.find(':');
        return stoi(timePoint.substr(0,pos)) * 60 + stoi(timePoint.substr(pos + 1));
    }
    int compare(int a, int b) {
        return (b - a + 1440) % 1440;
    }
public:
    int findMinDifference(vector<string>& timePoints) {
        vector<int> times;
        for(auto& timePoint : timePoints) {
            times.push_back(toTime(timePoint));
        }
        sort(begin(times), end(times));
        int n = times.size(), res = INT_MAX;
        for(int i = 0; i < n; i++) {
            res = min(res, compare(times[i], times[(i + 1) % n]));
        }
        return res;
    }
};

• Time : O(nlogn)
• Space : O(n)

class Solution {
    int parse(string& s) { //string to time with minites;
        return ((s[0] & 0b1111)*10 + (s[1] & 0b1111)) * 60 + (s[3] & 0b1111) * 10 + (s[4] & 0b1111);
    }
public:
    int findMinDifference(vector<string>& timePoints) {
        if(timePoints.size() >= 1441) return 0; //duplications
        int res = INT_MAX;
        set<int> s;
        for(auto& time : timePoints) {
            int minute = parse(time);
            if(s.empty()) { s.insert(minute);continue; }
            if(!res) return res;
            auto it = s.lower_bound(minute);
            if(it != s.end()) { //after minute
                res = min(res, *it - minute);
            } else {
                res = min(res, *s.begin() + 1440 - minute);
            }

            if(it == s.begin()) { //before minute
                res = min(res, minute + 1440 - *prev(s.end()));
            } else {
                res = min(res, minute - *prev(it));
            }
            s.insert(minute);
        }
        return res;
    }
};