Lập lịch họp trong C++

Cho danh sách khung giờ rảnh slots1, slots2 của hai người và thời lượng họp duration. Tìm khung giờ sớm nhất phù hợp cho cả hai (độ dài ≥ duration). Mỗi khung giờ là [start, end]. Các khung giờ của cùng một người không giao nhau.

Ví dụ: s1 = [[10,50],[60,120],[140,210]], s2 = [[0,15],[60,70]], duration = 8 → [60,68].

Thuật toán giải quyết (Hai con trỏ sau khi sắp xếp)

1. Sắp xếp cả hai mảng theo start tăng dần.
2. Hai con trỏ i, j duyệt slots1, slots2:
   • start = max(slots1[i][0], slots2[j][0]).
   • end = min(slots1[i][1], slots2[j][1]).
   • Nếu end - start >= duration → trả về [start, start+duration].
   • Ngược lại, loại bỏ khung giờ kết thúc sớm hơn: nếu slots1[i][1] < slots2[j][1] → i++; else j++.
3. Nếu không tìm thấy → trả về mảng rỗng.

Ví dụ minh họa (C++)

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

void print_vector(vector<auto> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) cout << v[i] << ", ";
    cout << "]" << endl;
}

bool cmp(vector<int> a, vector<int> b) { return a[0] < b[0]; }

class Solution {
public:
    vector<int> minAvailableDuration(vector<vector<int>>& slots1, vector<vector<int>>& slots2, int duration) {
        sort(slots1.begin(), slots1.end(), cmp);
        sort(slots2.begin(), slots2.end(), cmp);
        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() {
    vector<vector<int>> v = {{10,50},{60,120},{140,210}};
    vector<vector<int>> v1 = {{0,15},{60,70}};
    Solution ob;
    print_vector(ob.minAvailableDuration(v, v1, 8));
}

Đầu vào

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

Đầu ra

[60, 68, ]