Weighted interval scheduling when overlapping intervals are allowed?

I believe there isn’t a solution of polynomial complexity to this problem:

The question basically is that you have a cab company. It accepts bookings from K people. Every booking has a start time S and end time E. the profit the company gets by aaccepting ith booking is Ei-Si.

now, the company only has N cabs

where N

so for given K, N, and start time and end time

what is the max profit that company can make?



Is there a polynomial time solution? This isn’t a homework question, and appeared in a local contest. But I believe, for the constraints given, this can’t be solved.