Thời gian lớn nhất có thể tạo từ 4 chữ số trong C++

Cho 4 chữ số. Tạo thời gian hợp lệ định dạng 24h (HH:MM) lớn nhất.

Thuật toán (Tham lam + Backtracking nhẹ)

• Đếm tần suất 4 chữ số.
• Chọn giờ hàng chục: 2→0 (ưu tiên lớn). Nếu chọn 2, giờ hàng đơn vị 0-3.
• Chọn phút hàng chục: 5→0.
• Chọn phút hàng đơn vị: 9→0.
• Nếu bất kỳ bước nào thất bại → trả về "-1".

Ví dụ triển khai (C++)

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

map<int, int> getFreq(int arr[], int n) {
    map<int, int> mp;
    for (int i = 0; i < n; i++) mp[arr[i]]++;
    return mp;
}

bool take(map<int, int>& mp, int d) {
    if (mp[d]) { mp[d]--; return true; }
    return false;
}

string getMaxTime(int arr[], int n) {
    auto mp = getFreq(arr, n);
    string t = "";
    bool ok = false;
    for (int h1 = 2; h1 >= 0; h1--) if (take(mp, h1)) { t += '0'+h1; ok=true; break; }
    if (!ok) return "-1";
    ok = false;
    int start = (t[0]=='2') ? 3 : 9;
    for (int h2 = start; h2 >= 0; h2--) if (take(mp, h2)) { t += '0'+h2; ok=true; break; }
    if (!ok) return "-1";
    t += ':';
    ok = false;
    for (int m1 = 5; m1 >= 0; m1--) if (take(mp, m1)) { t += '0'+m1; ok=true; break; }
    if (!ok) return "-1";
    ok = false;
    for (int m2 = 9; m2 >= 0; m2--) if (take(mp, m2)) { t += '0'+m2; ok=true; break; }
    if (!ok) return "-1";
    return t;
}

int main() {
    int arr[] = {0,0,0,9};
    int n = 4;
    cout << getMaxTime(arr, n);
    return 0;
}

Đầu ra

09:00