Next Closest Time – หาเวลาถัดไปที่ใช้ตัวเลขเดิมใน C++

ปัญหา: Next Closest Time

กำหนดเวลาในรูปแบบ "HH:MM" หาเวลาถัดไปที่ ใกล้ที่สุด โดยใช้ เฉพาะตัวเลขที่มีอยู่ในเวลาเดิม (ซ้ำได้ไม่จำกัด)

ตัวอย่าง

Input: "19:34" → ตัวเลขที่มี: {1,9,3,4}
Output: "19:39" (ไม่ใช่ 19:33 เพราะ 19:33 อยู่ในอดีต 23 ชม. 59 นาที)

แนวทางแก้ปัญหา: Brute Force ทุกความเป็นไปได้

ข้อสังเกต

• มีตัวเลขได้สูงสุด 4 ตัว (จาก HH:MM)
• เวลาที่เป็นไปได้ทั้งหมด: 4⁴ = 256 แบบ (HH: 00-23, MM: 00-59)
• Brute force ทุกคอมบิเนชัน → คำนวณความต่างเวลา → หาค่าน้อยที่สุด (> 0)

ขั้นตอน

1. ดึงตัวเลข 4 ตัวจากเวลา (ข้าม ':')
2. วนลูป 4 ชั้น (i,j,k,l) สร้าง HH:MM ทุกแบบ
3. กรอง: HH ≤ 23, MM ≤ 59
4. ข้ามเวลาเดิม
5. คำนวณ diff = (new - original) mod 1440 (นาทีใน 1 วัน)
6. เก็บ diff น้อยที่สุด

ตัวอย่างโค้ด C++

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

class Solution {
public:
    int toMinutes(const string& t) {
        int h = stoi(t.substr(0,2));
        int m = stoi(t.substr(3,2));
        return h * 60 + m;
    }

    string nextClosestTime(string time) {
        vector<char> digits = {time[0], time[1], time[3], time[4]};
        int original = toMinutes(time);
        int bestDiff = INT_MAX;
        string bestTime = "";

        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) - original;
            if (diff < 0) diff += 1440; // next day
            if (diff < bestDiff) {
                bestDiff = diff;
                bestTime = cand;
            }
        }
        return bestTime.empty() ? time : bestTime;
    }
};

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

โค้ดต้นฉบับ (มีบั๊กเล็กน้อยใน eval)

// eval function ในต้นฉบับมีปัญหา: to_string(x[0]) จะแปลง char '1' -> "49" (ASCII)
// ควรใช้ string(1, x[0]) แทน

ความซับซ้อน

• เวลา: O(1) – 256 iterations คงที่
• พื้นที่: O(1)

ข้อสังเกต

• LeetCode 681
• วิธีอีกวิธี: บวก 1 นาทีทีละนาทีจนกว่าจะเจอเวลาที่ใช้ตัวเลขเดิมได้ (สูงสุด 1440 รอบ)
• Brute force 256 แบบ เร็วกว่าและง่ายกว่า
• Edge case: "23:59" → "22:22" (ถ้าตัวเลขมี 2,3,5,9)