Microsoft - MaxEmployeeAttendence (R repititions - Semi Optimised DP), C++ (gcc)

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

λ

                                      .NET NoSQL database for rapid development