Hello Community,
I had a first coding interview with Google (Munich) and I was asked a question which I was not able to solve. After receiving many hints from interviewer I was at least able to write brute force solution. I am trying to find the problem on internet but I am not able to find anything similar. Can someone help me find the problem/solution somewhere?
Question:
You have an on call calendar which has range of hours which is not covered by company's engineers and company wants to hire a contractor.
Contractor can serve Q hours and it can not be split in multiple shifts. So if you hire a contractor for Q-2 hours then you can not hire contractor again.
Goal is to minimize the uncovered hours and return it.
Anyone know where can I find similar problem/solution ?
Thanks in advance.
Input: int[][] cal; int Q
Minimize the uncovered hours for next 100 hours;
We have an input like this: int[][] cal = [[0, 5], [7, 10], [11, 15], [20, 100]]
This means online calendar for next 100 hours is fixed.
cal[i] represents employee i wll be on call from hour cal[i][0] to cal[i][1].
And that means from hour 5 to 7 and 15 to 20 no one will be on call. Total 7 hours uncovered.
Now we have given one more integer Q. Meaning we can hire one contractor who can serve Q hours.
Contractor can only serve once - means contractor can serve only one shift of maximum Q hours. So let's say for above example Q = 10 then if we assign contractor from 5 to 7 then contractor will be only serving two hours and uncovered hours will become 5 but if we assign contractor from 15 to 20 hours - then contractor can serve 5 hours and uncovered hours will become 2 which is accepted answer.
Contractor can also overlap existing duties of employee and we don't care for that - means if you assign contractor for already assigned shift in the essenece to minimize the uncovered hours - this is okay. Let's modify above example little bit:
int[][] cal = [[0, 5], [7, 10], [15, 16], [20, 100]] and Q = 10; So you can assign contracto from 5 to 15 and that way contractor serves (7 - 5) + (15 - 10) = 7 hours. Though employee i = 1's duty will be overlapped but that's not a problem.
Please ask if you have further questions.