hw5/schedwork.cpp at main · primjim1234/hw5 · GitHub

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#ifndef RECCHECK
#include <set>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#endif

#include "schedwork.h"

using namespace std;

static const Worker_T INVALID_ID = (unsigned int)-1;

static bool scheduleHelper(
    const AvailabilityMatrix& avail,
    size_t dailyNeed,
    size_t maxShifts,
    DailySchedule& sched,
    std::vector<size_t>& shiftsUsed,
    size_t day,
    size_t slot
);

bool schedule(
    const AvailabilityMatrix& avail,
    const size_t dailyNeed,
    const size_t maxShifts,
    DailySchedule& sched
)
{
    if(avail.size() == 0U || dailyNeed == 0U){
        return false;
    }

    size_t n = avail.size();
    size_t k = avail[0].size();

    sched.clear();
    sched.assign(n, std::vector<Worker_T>(dailyNeed, INVALID_ID));

    std::vector<size_t> shiftsUsed(k, 0);

    if(scheduleHelper(avail, dailyNeed, maxShifts, sched, shiftsUsed, 0, 0)){
        return true;
    }

    return false;
}

static bool scheduleHelper(
    const AvailabilityMatrix& avail,
    size_t dailyNeed,
    size_t maxShifts,
    DailySchedule& sched,
    std::vector<size_t>& shiftsUsed,
    size_t day,
    size_t slot
)
{
    size_t n = avail.size();
    size_t k = avail[0].size();

    if(day == n){
        return true;
    }

    if(slot == dailyNeed){
        return scheduleHelper(avail, dailyNeed, maxShifts, sched, shiftsUsed, day + 1, 0);
    }

    for(size_t w = 0; w < k; ++w){
        if(!avail[day][w]){
            continue;
        }
        if(shiftsUsed[w] >= maxShifts){
            continue;
        }
        if(std::find(sched[day].begin(), sched[day].end(), w) != sched[day].end()){
            continue;
        }

        sched[day][slot] = static_cast<Worker_T>(w);
        shiftsUsed[w]++;

        if(scheduleHelper(avail, dailyNeed, maxShifts, sched, shiftsUsed, day, slot + 1)){
            return true;
        }

        shiftsUsed[w]--;
        sched[day][slot] = INVALID_ID;
    }

    return false;
}