Meeting Scheduler ใน C++: หาช่วงเวลาว่างร่วมที่เร็วที่สุด

โจทย์

กำหนดช่วงเวลาว่างของคน 2 คน (slots1, slots2) และระยะเวลาประชุม duration หาช่วงเวลาที่ทั้งคู่ว่างร่วมกันและยาวพอ ไปที่เร็วที่สุด

รูปแบบช่วง: [start, end] (inclusive) ไม่มีช่วงทับซ้อนในคนเดียวกัน

ตัวอย่าง: slots1=[[10,50],[60,120],[140,210]], slots2=[[0,15],[60,70]], duration=8 → [60,68]

แนวคิด: Two Pointers หลังเรียงตามเวลาเริ่มต้น

เรียงทั้งสองรายการตาม start time แล้วใช้ 2 pointers เดินไปพร้อมกัน หาช่วงทับซ้อน

ขั้นตอน

1. เรียง slots1 และ slots2 ตาม start
2. i = 0, j = 0
3. while i < slots1.size() && j < slots2.size():
   • start = max(slots1[i][0], slots2[j][0])
   • end = min(slots1[i][1], slots2[j][1])
   • ถ้า end - start >= duration → คืน [start, start + duration]
   • ถ้า slots1[i][1] < slots2[j][1] → i++ ไม่งั้น j++
4. คืน empty array ถ้าไม่พบ

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

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

void print_vector(vector<int> v) {
    cout << "[";
    for (int x : v) cout << x << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> minAvailableDuration(vector<vector<int>>& slots1, 
                                     vector<vector<int>>& slots2, int duration) {
        sort(slots1.begin(), slots1.end());
        sort(slots2.begin(), slots2.end());
        
        int i = 0, j = 0;
        while (i < slots1.size() && j < slots2.size()) {
            int start = max(slots1[i][0], slots2[j][0]);
            int end = min(slots1[i][1], slots2[j][1]);
            
            if (end - start >= duration) {
                return {start, start + duration};
            }
            
            if (slots1[i][1] < slots2[j][1]) i++;
            else j++;
        }
        return {};
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v1 = {{10,50},{60,120},{140,210}};
    vector<vector<int>> v2 = {{0,15},{60,70}};
    print_vector(ob.minAvailableDuration(v1, v2, 8)); // [60, 68]
    return 0;
}

อินพุต / เอาต์พุต

Input: [[10,50],[60,120],[140,210]] [[0,15],[60,70]] 8

Output: [60, 68]

ความซับซ้อน

• Time: O(m log m + n log n) - เรียงลำดับ
• Space: O(1) extra