I've recently taken an OA in which you needed to write an algorithm for finding the earliest time at which you were able to complete one task from each category. Each task has a duration and a time at which it's going to be available (release time). You need to do the tasks sequentially.
An example of input:
// There could be more than 2 tasks in a category, this is just an example.
// The OA had only two categories, but I think a good solution would be able to handle an arbitrary amount.
catOneReleaseTime = [1, 4] // release times of the two tasks in category one
catOneDuration = [3, 2] // duration times of the two tasks in category one
catTwoReleaseTime = [5, 2]
catTwoDuration = [2, 2]
The difficulty of the problem comes from the fact that things might overlap, I think.
I suspect this is either a dynamic programming or a greedy algorithm problem, but, quite frankly, I really don't know how to solve it. Something tells me I would need to do some kind of sorting as well, but I don't know since there are two dimensions for me to sort through. At the time of the OA, I used brute force to half-solve it, but I couldn't get full marks because my solution would time out on some test cases.
Note that though this does indeed look similar to these Leet Code questions, I don't think it is either:
With 2 categories you can solve it in O(n + m) and I'm pretty sure you can't get better than that:
Calculate soonest end time for both categories:
sX = min(catXreleaseTime[i] + catXDuration[i])
Calculate soonest end time when starting with the other category's soonest end time and return the smaller value:
eY = min(max(sX, catYreleaseTime[i]) + catYDuration[i])
Like this the sorting is avoided, the tasks are just iterated twice. I somehow doubt there is a polynomial solution for an arbitrary number of categories.