Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Microsoft - MaxEmployeeAttendence (R repititions - Semi Optimised DP)
//g++ 7.4.0 // https://leetcode.com/discuss/interview-experience/1930164/Microsoft-or-SDE2-or-Hyderabad-or-April-2022-Reject #include <bits/stdc++.h> using namespace std; const int MAX_DAYS = 10; const int MAX_REPITITIONS = 10; const int MAX_EMPLOYEES = 10; int dp[MAX_DAYS][MAX_REPITITIONS][1 << MAX_DAYS]; vector<vector<int>> availability; int total_days; int NumberOfEmployeesAvailable(int selected_days_mask) { unordered_set<int> selected_days_set; for (int i = 0; i < total_days; i ++) { bool ith_bit_set = ((1 << i) & selected_days_mask) != 0; if (!ith_bit_set) continue; selected_days_set.insert (i); } int unique_employees = 0; for (int employee = 0; employee < availability.size(); employee ++) { for (int day : availability[employee]) { if (selected_days_set.count(day) != 0) { unique_employees ++; break; } } } return unique_employees; } int MaxEmployeeAttendence (int current_day, int repititions_left, int selected_days_mask) { if (repititions_left == 0) { return NumberOfEmployeesAvailable (selected_days_mask); } if (current_day < 0) return 0; // There are no more days & we haven't organised the course for required `repititions`. int& result = dp[current_day][repititions_left][selected_days_mask]; if (result != -1) return result; result = 0; // take the current day result = max (result, MaxEmployeeAttendence(current_day-1, repititions_left-1, selected_days_mask | (1 << current_day))); // don't take the current day result = max (result, MaxEmployeeAttendence(current_day-1, repititions_left, selected_days_mask)); return result; } /* * availability[i] - list of days on which ith employee will be available to take the training. [0 <= availability[i][j] < D] * * total_days (D) - total number of days in which the training can be conducted. * * repititions (R) - number of times the training will be repeated in 'total_days' duration. * **/ int MaxEmployeeAttendence (vector<vector<int>>& _availability, int _total_days, int repititions) { availability = _availability; total_days = _total_days; memset(dp, -1, sizeof(dp)); return MaxEmployeeAttendence (total_days-1, repititions, 0); } int main() { vector<vector<int>> availability = { {0, 3, 9}, {4}, {1, 4}, {3, 2}, {3, 4}, {7} }; cout << MaxEmployeeAttendence (availability, 10, 2) << endl; return 0; }
run
|
edit
|
history
|
help
0
k1
Reminder
Splitwise Problem - 1
Test
kadane's algorithm
Synchro#3
Backtracking_simple
substr
Best way for getting more precision no.
protected