Employee Free Time (เวลาว่างของพนักงาน) ใน C++

สมมติว่าเราได้รับรายการตารางเวลาของพนักงาน ซึ่งแสดงถึงเวลาทำงานของแต่ละพนักงาน ตอนนี้สมมติว่าแต่ละพนักงานมีรายการของ Intervals ที่ไม่ทับซ้อนกัน และ intervals เหล่านี้เรียงลำดับแล้ว เราต้องหา รายการของ finite intervals ที่แสดงถึง เวลาว่างร่วมกัน (common free time) ที่มีความยาวบวก สำหรับพนักงานทุกคน และจะเรียงลำดับด้วย เราแทน Intervals ในรูปแบบ [x, y] ตัวอย่างเช่น schedule[0][0].start = 1, schedule[0][0].end = 2

ดังนั้น หากอินพุทคือ schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]] ผลลัพธ์หนึ่งในจะเป็น [[3,4]]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:

• กำหนดอาเรย์ 2 มิติ v

• for i := 0 ถึง schedule.size()-1, for j := 0 ถึง schedule[i].size()-1: ใส่ schedule[i][j] ลง v

• จัดเรียง v

• กำหนดอาเรย์ 2 มิติ ret

• กำหนดอาเรย์ temp := v[0]

• for i := 0 ถึง v.size()-1:

  • ถ้า temp[0] < v[i][1]: ใส่ {temp[1], v[i][0]} ลง ret; temp := v[i]

  • มิฉะนั้น: temp := (temp[1] < v[i][1]) ? v[i] : temp

• คืนค่า ret

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

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

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

class Solution {
public:
    static bool cmp(vector a, vector b) {
        return a[0] < b[0];
    }

    vector> employeeFreeTime(vector>> schedule) {
        vector> v;
        for (int i = 0; i < schedule.size(); i++) {
            for (int j = 0; j < schedule[i].size(); j++) {
                v.push_back(schedule[i][j]);
            }
        }
        sort(v.begin(), v.end(), cmp);
        vector> ret;
        vector temp = v[0];
        for (int i = 0; i < v.size(); i++) {
            if (temp[0] < v[i][1]) {
                ret.push_back({temp[1], v[i][0]});
                temp = v[i];
            } else {
                temp = temp[1] < v[i][1] ? v[i] : temp;
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector>> v = {{{1,2},{5,6}},{{1,3}},{{4,10}}};
    print_vector(ob.employeeFreeTime(v));
    return 0;
}

อินพุต

{{{1,2},{5,6}},{{1,3}},{{4,10}}}

เอาต์พุต

[[2, 1, ],[2, 1, ],[3, 4, ],[10, 5, ],]