Problem: What is the maximum number of meetings that can be accommodated in one meeting room?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | #include <bits/stdc++.h> using namespace std; struct meeting { int start; int end; int pos; }; bool comparator(struct meeting m1, meeting m2) { return (m1.end < m2.end); } void maxMeeting(int s[], int f[], int n) { struct meeting meet[n]; for (int i = 0; i < n; i++) { // Starting time of meeting i. meet[i].start = s[i]; // Finishing time of meeting i meet[i].end = f[i]; // Original position/index of meeting meet[i].pos = i + 1; } // Sorting of meeting according to their finish time. sort(meet, meet + n, comparator); // Vector for storing selected meeting. vector<int> m; // Initially select first meeting. m.push_back(meet[0].pos); int time_limit = meet[0].end; for (int i = 1; i < n; i++) { if (meet[i].start >= time_limit) { // Push selected meeting to vector m.push_back(meet[i].pos); // Update time limit. time_limit = meet[i].end; } } // Print final selected meetings. for (int i = 0; i < m.size(); i++) { cout << m[i] << " "; } } // Driver code int main() { // Starting time int s[] = { 1, 3, 0, 5, 8, 5 }; // Finish time int f[] = { 2, 4, 6, 7, 9, 9 }; // Number of meetings. int n = sizeof(s) / sizeof(s[0]); // Function call maxMeeting(s, f, n); return 0; } |
Program Output
1 | 1 2 4 5 |
If you like this question & answer and want to contribute, then write your question & answer and email to freewebmentor[@]gmail.com. Your question and answer will appear on FreeWebMentor.com and help other developers.
