If I'm understanding it, the requirement as specified sounds fundamentally row-by-row as you must know what the previous row in the sequence did in order to process the next row, so a recursive CTE is likely to be as bad or worse than a well optimised cursor.

As Hugo says, if there was a less rigid requirement for the priority of each request, then you could perform recursion/looping over sets rather than over rows, massively reducing the iteration and improving the performance.

I think Kevin's code helps with finding the first individual gap in a schedule, but not in fitting a batch of requests into a schedule in a specific priority order.