Thời gian tiếp theo gần nhất trong C++

Giới thiệu

Cho thời gian dạng "HH:MM". Tìm thời gian tiếp theo gần nhất (theo chiều kim đồng hồ) có thể tạo bằng cách dùng lại các chữ số hiện có (mỗi chữ số dùng không giới hạn lần).

Thuật toán: Thử tất cả tổ hợp (Brute Force)

Chỉ có 4 chữ số → 4^4 = 256 tổ hợp khả thi. Thử tất cả cặp (HH, MM) hợp lệ (00-23, 00-59), tính độ chênh lệch phút so với thời gian gốc, chọn cái có độ chênh lệch dương nhỏ nhất.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
    int toMinutes(string t) {
        return stoi(t.substr(0,2)) * 60 + stoi(t.substr(3,2));
    }
public:
    string nextClosestTime(string time) {
        vector digits = {time[0], time[1], time[3], time[4]};
        int start = toMinutes(time);
        int bestDiff = INT_MAX;
        string ans = time;
        for (char h1 : digits) for (char h2 : digits)
        for (char m1 : digits) for (char m2 : digits) {
            string hh = string(1,h1)+h2;
            string mm = string(1,m1)+m2;
            int h = stoi(hh), m = stoi(mm);
            if (h > 23 || m > 59) continue;
            string cand = hh + ":" + mm;
            if (cand == time) continue;
            int diff = toMinutes(cand) - start;
            if (diff < 0) diff += 24*60; // ngày hôm sau
            if (diff < bestDiff) {
                bestDiff = diff;
                ans = cand;
            }
        }
        return ans;
    }
};

int main() {
    Solution ob;
    cout << ob.nextClosestTime("19:34"); // Output: 19:39
    return 0;
}

Phân tích

• Thời gian: O(1) – 256 vòng lặp cố định.
• Không gian: O(1).

LeetCode 681 "Next Closest Time".