I was recently faced with a hackerrank interview test where I couldn't solve the following problem correctly. I would not want to name the exact problem for privacy purposes, but I can tell that it was nowhere in Google with this name.
We want to organize an event with as much performers as possible. We are given a list of possible performer arrival times and performance durations. Our function should return the maximum number of performers that can be selected without conflicts.
N = 5
arrivals = [1, 3, 3, 5, 7] (performers arrive in these times)
durations = [2, 2, 1, 2, 1] (the time needed to finish their performances)
solution = 4
So at time 1 we can accept the performer and will finish at time 3. At time 3 we have two conflicting choices, and doesn't matter which we chose. Time 5 and 7 are not conflicted either.
- Made tuples of the arrivals and durations by zipping. Sorted the tuples first on arrival, then on duration.
- Outer for cycle for i from start to finish. Initialize new set in each iter.
- Inner for cycle for j from i to finish. Check if j can be added to the set without conflict. If set is longer than max I save.
- Are there better ways, standard algorithms to solve this problem?
- I know that there are some edge cases, for which my algorithm doesn't work. Hackerrank evaluated my algo, and it only passed 7/13 test cases. What could be some edge cases I am missing?
- Is this a search problem or an optimization problem?