Minimum Time Difference หาความต่างเวลาน้อยที่สุดใน C++

ให้ลิสต์เวลาในรูปแบบ "Hour:Minutes" 24 ชั่วโมง หาความต่างน้อยที่สุดในหน่วยนาทีระหว่างเวลาใดๆ สองเวลาในลิสต์

ตัวอย่าง: ["12:30","15:17"] → 167 นาที

วิธีแก้ปัญหา (Bucket Sort / Boolean Array)

1. สร้างอาร์เรย์ ok ขนาด 24*60+1 = 1441 ทั้งหมด false
2. วนแปลงแต่ละเวลาเป็นนาที (hr*60 + min):
   • ถ้า ok[time] เป็น true แล้ว → คืน 0 (มีเวลาซ้ำ)
   • ตั้ง ok[time] = true
3. วน i = 0 ถึง 1440:
   • ถ้า ok[i] เป็น true:
     • อัปเดต first (เวลาแรก), last (เวลาสุดท้าย)
     • คำนวณความต่างกับ prev (เวลาก่อนหน้า)
4. คืนค่า min(ret, 24*60 + first - last) // พิจารณาเวลาข้ามเที่ยงคืน

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

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

class Solution {
public:
    int findMinDifference(vector<string>& tp) {
        vector<bool> ok(24 * 60 + 1, false);
        int n = tp.size();
        for (int i = 0; i < n; i++) {
            int hr = stoi(tp[i].substr(0, 2));
            int min = stoi(tp[i].substr(3, 2));
            int time = hr * 60 + min;
            if (ok[time]) return 0;
            ok[time] = true;
        }
        int last = 0, first = INT_MAX, ret = INT_MAX, prev = INT_MIN;
        for (int i = 0; i <= 24 * 60; i++) {
            if (ok[i]) {
                last = max(i, last);
                first = min(i, first);
                if (prev != INT_MIN) ret = min(ret, last - prev);
                prev = i;
            }
        }
        return min(ret, 24 * 60 + first - last);
    }
};

int main() {
    vector<string> v = {"12:30","15:17"};
    Solution ob;
    cout << ob.findMinDifference(v);
    return 0;
}

Input

["12:30","15:17"]

Output

167