Recently, I heard of a google interview question from my friend and was wondering about the solution but could come up with any. Any hints on this is appreciated. So the questions goes like this-

You are given some an array of segments (S), which basically represents time. There is no overlapping between the segments. You are given number of workers(k) who can work for q duration in one go. The workers would work for q duration straight to cover the given segments. We need to return the minimum number of uncovered segments.

Sample Test-

S — [3-12], [18-24], [30-35], k=2, q=7
OUTPUT- 1

Explanation- Segment 2 and 3 will get entirely covered.

S- [3-5], [8-9], [15-16], [17-25], [27-30] k=2, q=7, OUTPUT- 2

Explanation- Segment 1 and 2 will get covered by one worker, then either segment 3 or 5 can be covered by the other worker