Giả sử chúng ta được cho danh sách lịch trình của nhân viên; điều này đại diện cho thời gian làm việc của mỗi nhân viên. Giả sử mỗi nhân viên có danh sách các Interval không chồng chéo, các khoảng thời gian này được sắp xếp. Chúng ta phải tìm danh sách các khoảng thời gian hữu hạn đại diện cho thời gian rảnh chung, độ dài dương cho tất cả nhân viên, và cũng sẽ được theo thứ tự sắp xếp. Chúng ta biểu diễn Intervals dưới dạng [x, y], Ví dụ, schedule[0][0].start = 1, schedule[0][0].end = 2.
Vì vậy, nếu đầu vào là schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]], một trong các đầu ra sẽ là [[3,4]].
Để giải quyết, chúng ta sẽ làm theo các bước:
Định nghĩa mảng 2D v
Khởi tạo i := 0, khi i < kích thước schedule, cập nhật (tăng i lên 1), làm
Khởi tạo j := 0, khi j < kích thước schedule[i], cập nhật (tăng j lên 1), làm
Chèn schedule[i, j] vào cuối v
Sắp xếp mảng v
Định nghĩa mảng 2D ret
Định nghĩa mảng temp := v[0]
Khởi tạo i := 0, khi i < kích thước v, cập nhật (tăng i lên 1), làm:
nếu temp[0] < v[i, 1], thì:
Chèn {temp[1], v[i, 0]} vào cuối ret
temp := v[i]
Ngược lại
temp := (nếu temp[1] < v[i, 1], thì v[i], ngược lại temp)
Trả về ret
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
#include <bits/stdc++.h> using namespace std; void print_vector(vector<vector<auto> > 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<int> a, vector<int> b){ return a[0] < b[0]; } vector<vector<int>> employeeFreeTime(vector<vector<vector<int>>> schedule) { vector<vector<int>> 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<vector<int>> ret; vector<int> 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; } }; main(){ Solution ob; vector<vector<vector<int>>> v = {{{1,2},{5,6}},{{1,3}},{{4,10}}}; print_vector(ob.employeeFreeTime(v)); }Đầu vào
{{{1,2},{5,6}},{{1,3}},{{4,10}}}Đầu ra
[[2, 1, ],[2, 1, ],[3, 4, ],[10, 5, ],]