मान लीजिए हमें कर्मचारियों की शेड्यूल की एक सूची दी गई है; यह प्रत्येक कर्मचारी के लिए कार्य समय का प्रतिनिधित्व करता है। अब मान लीजिए प्रत्येक कर्मचारी के पास नॉन-ओवरलैपिंग अंतराल की एक सूची है, ये अंतराल सॉर्टेड हैं। हमें सभी कर्मचारियों के लिए सामान्य, पॉजिटिव-लेंथ फ्री टाइम का प्रतिनिधित्व करने वाले परिमित अंतराल की सूची ज्ञात करनी है, और वह भी सॉर्टेड ऑर्डर में होगी। हम अंतराल को [x, y] के रूप में दर्शा रहे हैं, उदाहरण के लिए, schedule[0][0].start = 1, schedule[0][0].end = 2।
तो, यदि इनपुट schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]] है, तो आउटपुट में से एक [[3,4]] होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
एक 2D ऐरे v परिभाषित करें
i := 0 से शुरू करें, जब i < schedule का आकार, अपडेट करें (i को 1 से बढ़ाएं), करें:
j := 0 से शुरू करें, जब j < schedule[i] का आकार, अपडेट करें (j को 1 से बढ़ाएं), करें:
schedule[i, j] को v के अंत में डालें
ऐरे v को सॉर्ट करें
एक 2D ऐरे ret परिभाषित करें
एक ऐरे टेम्प := v[0] परिभाषित करें
i := 0 से शुरू करें, जब i < v का आकार, अपडेट करें (i को 1 से बढ़ाएं), करें:
यदि टेम्प[0] < v[i, 1], तो:
{टेम्प[1], v[i, 0]} को ret के अंत में डालें
टेम्प := v[i]
अन्यथा:
टेम्प := (यदि टेम्प[1] < v[i, 1], तो v[i], अन्यथा टेम्प)
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)); }
इनपुट
{{{1,2},{5,6}},{{1,3}},{{4,10}}}
आउटपुट
[[2, 1, ],[2, 1, ],[3, 4, ],[10, 5, ],]