Schedule of teachers and subjects X84909
The input of this exercise will have one or more lines, where each one of them specifies a class given by a teacher along the week. More specifically, each line has a name of a subject, a name of a teacher, a day of the week, a starting hour and an ending hour. For example:
algebra joel monday 8 10 physics guille thursday 10 14 programming guille thursday 11 13 programming nuria thursday 12 14 statistics silvia tuesday 9 10 deeplearning silvia tuesday 8 10
For the sake of simplicity, names of subjects and teachers are strings of lowercase letters. The days of the week are always in {monday,tuesday,wednesday,thursday,friday}. The two hours h1,h2 always hold h1<h2 and are in the set {0,…,24}.
As you can see on former example, there may be repetitions of subjects and conflicts of teachers (a subject may be given simultaneously more than once, and a teacher may be assigned to more than one simultaneous class).
The first part of the output will have a description as a table of how many classes are being given at each hour of the week. The first column (h) has width 2 and is used to describe the starting time. The following 5 columns have width 10 each and are used for each day of the week. All columns are right-justified. Each row shows the information of a concrete hour. The hours shown are only those in the interval starting from the first one where a class is given until the last one where a class is still being given. This would be the result corresponding to former example:
number of subjects per slot: h monday tuesday wednesday thursday friday 8 1 1 0 0 0 9 1 2 0 0 0 10 0 0 0 1 0 11 0 0 0 2 0 12 0 0 0 3 0 13 0 0 0 2 0
In a second part of the output we have a table with the same format, but this time each cell shows the number of different teachers giving class at that particular hour and day (that is, the number of teachers giving class that hour and day after having removed repetitions). This would be the result corresponding to former example:
number of teachers per slot: h monday tuesday wednesday thursday friday 8 1 1 0 0 0 9 1 1 0 0 0 10 0 0 0 1 0 11 0 0 0 1 0 12 0 0 0 2 0 13 0 0 0 2 0
Finally, the output has a natural, which is the minimum number of hours of class where we need to replace current professor with a new one in order to avoid conflicts, that is, in order to prevent any teacher from being giving two classes simultaneously. This would be the result corresponding to former example:
number of replacements needed to avoid conflicts: 3
In order to solve this exercise, it is compulsory to conveniently use the following data structures. Otherwise, the delivery will be invalidated.
struct Slot {
vector<string> listsubjects;
vector<string> listteachers;
};
typedef vector<vector<Slot> > TableSlots;
Input
The input has already been described in the statement of the exercise. Take a look at the public data tests in order to get the hang of it.
Output
The output has already been described in the statement of the exercise. Take a look at the public data tests in order to get the hang of it.
Observation
Grading up to 10 points:
- Slow solution: 5 points.
- Fast solution: 10 points.
We understand as a fast solution one which is correct, with nlog(n) cost and which passes the public and private tests. We understand as slow solution one which is not fast, but it is correct and passes the public tests.
Input
algebra joel monday 8 10 physics guille thursday 10 14 programming guille thursday 11 13 programming nuria thursday 12 14 statistics silvia tuesday 9 10 deeplearning silvia tuesday 8 10
Output
number of subjects per slot: h monday tuesday wednesday thursday friday 8 1 1 0 0 0 9 1 2 0 0 0 10 0 0 0 1 0 11 0 0 0 2 0 12 0 0 0 3 0 13 0 0 0 2 0 number of teachers per slot: h monday tuesday wednesday thursday friday 8 1 1 0 0 0 9 1 1 0 0 0 10 0 0 0 1 0 11 0 0 0 1 0 12 0 0 0 2 0 13 0 0 0 2 0 number of replacements needed to avoid conflicts: 3
Input
algebra jose wednesday 19 23 analysis jose wednesday 9 11 history sonia monday 19 23 analysis nuria tuesday 4 6 programming merce wednesday 21 24 biology guille thursday 19 20 physics jordi wednesday 18 23 music laia tuesday 19 22 analysis manel tuesday 23 24 biology merce friday 11 12 analysis jose tuesday 20 22 geometry guille monday 4 6 philosphy nuria friday 15 17 music jose friday 1 4 pedagogy nuria wednesday 9 14 biology angels friday 3 4 history manel tuesday 2 6 geometry manel tuesday 2 7 philosphy nuria tuesday 0 5 biology jose tuesday 6 11 analysis oscar friday 10 13 physics guille wednesday 21 24 physics ferran tuesday 8 10 botanics nuria friday 4 9 pedagogy serge tuesday 13 16 analysis sandra monday 21 24 algebra jose wednesday 9 11 pedagogy jose thursday 11 16 algebra sandra wednesday 5 9 music nuria thursday 4 5 biology serge tuesday 11 15 computers ferran tuesday 1 2 analysis laia friday 20 22 physics laia monday 2 7 history joel wednesday 8 12 pedagogy guille monday 3 5 pedagogy ferran wednesday 4 5 physics serge tuesday 2 3 philosphy sonia monday 1 5 computers manel tuesday 0 5 algebra joel thursday 19 23 philosphy ferran monday 16 20 analysis manel friday 21 24 analysis angels thursday 6 10 physics angels wednesday 5 10 botanics laura friday 2 4 computers guille wednesday 8 11 geometry nuria friday 20 22 music manel friday 15 17 history oscar wednesday 23 24 music jose tuesday 18 22 computers nuria tuesday 4 6 biology laura thursday 16 19 pedagogy angels wednesday 6 11 botanics sandra wednesday 11 16 arts merce tuesday 21 23 arts oscar thursday 14 15 history joel tuesday 11 13 analysis manel thursday 12 13 geometry ferran tuesday 20 21 programming angels tuesday 6 8 geometry nuria tuesday 19 23 botanics guille thursday 4 9 programming ferran monday 6 9 physics sandra thursday 12 14 philosphy angels friday 9 14 philosphy jose monday 11 12 geometry guille monday 0 4 algebra joel wednesday 5 7 physics nuria friday 4 7 history laura monday 9 12 analysis oscar wednesday 2 6 pedagogy laura friday 14 19 geometry serge tuesday 12 13 computers joel friday 17 21 analysis nuria monday 4 7 biology joel thursday 13 15 computers angels thursday 1 6 programming serge friday 10 13 analysis angels tuesday 18 22 programming joel wednesday 12 16 pedagogy sandra thursday 1 5 programming laia thursday 8 9 history sonia tuesday 8 13 botanics sandra thursday 5 10 computers laia thursday 3 6 pedagogy sonia tuesday 21 24 pedagogy oscar thursday 21 24 arts nuria friday 9 10 analysis merce wednesday 2 6 analysis guille friday 9 14 history angels wednesday 12 16 physics ferran wednesday 18 23 physics laura friday 19 22 programming jordi friday 5 10 physics laura friday 23 24 analysis oscar thursday 11 16 history guille thursday 12 13 algebra serge friday 22 24 botanics sandra friday 2 5
Output
number of subjects per slot: h monday tuesday wednesday thursday friday 0 1 2 0 0 0 1 2 3 0 2 1 2 3 5 2 2 3 3 4 4 2 3 4 4 5 6 3 5 3 5 3 4 5 4 3 6 3 3 4 3 3 7 1 2 3 3 2 8 1 3 5 4 2 9 1 3 7 2 4 10 1 2 6 0 4 11 2 3 3 2 5 12 0 4 4 5 4 13 0 2 4 4 2 14 0 2 3 4 1 15 0 1 3 2 3 16 1 0 0 1 3 17 1 0 0 1 2 18 1 2 2 1 2 19 2 4 3 2 2 20 1 6 3 1 4 21 2 7 5 2 4 22 2 3 5 2 2 23 1 2 3 1 3 number of teachers per slot: h monday tuesday wednesday thursday friday 0 1 2 0 0 0 1 2 3 0 2 1 2 3 3 2 2 3 3 3 2 2 3 4 4 4 2 3 5 2 5 3 2 5 4 2 6 3 3 3 3 2 7 1 2 2 3 2 8 1 3 4 4 2 9 1 3 5 2 4 10 1 2 5 0 4 11 2 3 3 2 5 12 0 3 4 5 4 13 0 1 4 4 2 14 0 1 3 3 1 15 0 1 3 2 3 16 1 0 0 1 3 17 1 0 0 1 2 18 1 2 2 1 2 19 2 4 3 2 2 20 1 5 3 1 4 21 2 6 5 2 4 22 2 3 5 2 2 23 1 2 3 1 3 number of replacements needed to avoid conflicts: 27