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?
K<500
N<100
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.