首页 > itarticle > lc 539. minimum time difference

lc 539. minimum time difference

admin 11月 13, 2020 0

Description

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

Brute-force one- TLE

class  {
public:
    int diff(vector<int> time1, vector<int> time2){
        if(time1[0] > time2[0] || (time1[0] == time2[0] && time1[1] > time2[1])){
            vector<int> temp = time1;
            time1 = time2;
            time2 = temp;
        }
        int hdiff = (time2[0] - time1[0]) * 60;
        int mdiff = time2[1] - time1[1];
        return 24 * 60 - (hdiff + mdiff) > hdiff + mdiff ? hdiff + mdiff : 24*60 - (hdiff + mdiff);
    }
    static bool comp(vector<int> time1, vector<int> time2){
        return time1[0] < time2[0] || (time1[0] == time2[0] && time1[1] < time2[1]);
    }
    int findMinDifference(vector<string>& timePoints) {
        vector<vector<int>> times;
        for(string t : timePoints){
            stringstream ss(t);
            string part;
            vector<string> hm;
            while(getline(ss, part, ':')){
                hm.push_back(part);
            }
            int hour = stoi(hm[0]);
            int min =  stoi(hm[1]);
            times.push_back({hour, min});
        }
        int minimum = INT_MAX;
        for(int i = 0; i < times.size(); i++){
            for(int j = i + 1; j < times.size(); j++){
                minimum = min(minimum, diff(times[i], times[j]));
            }
        }
        return minimum;
    }
};

Better Solution : slot - fixed-length array is very useful

class  {
public:
    int findMinDifference(vector<string>& timePoints) {
        vector<bool> timeSlot(24*60, false);
        for(string s : timePoints){
            stringstream ss(s);
            string part;
            vector<string> tp;
            while(getline(ss, part, ':')){
                tp.push_back(part);
            }
            int hour = stoi(tp[0]);
            int mini = stoi(tp[1]);
            if(timeSlot[hour*60+mini])
                return 0;
            timeSlot[hour*60+mini] = true;
        }
        int first = INT_MAX, last = INT_MIN;
        int res = INT_MAX, pre = 0;
        for(int i = 0; i < timeSlot.size(); i++){
            if(timeSlot[i]){
                if(first != INT_MAX){
                    res = min(res, i - pre);
                }
                first = min(first, i);
                last = max(last, i);
                pre = i;
            }
        }
        return min(res, 24*60-last+first);
    }
};