# Can interval partition solve by sort by different approach

The interval partitioning problem is described as follows: Given a set {1, 2, …, n} of n requests, where ith request starts at time s(i) and finishes at time f(i), find the minimum number of resources needed to schedule all requests so that no two requests are assigned to the same resource at the same time.

I read from many sources, that the solution often is:

- sort again by earliest time of requests.
- For each requests in sorted request:
if can choose one resource that can do this requests:
assign that request to resource
else
create new resource
count++
assign that request to new resource


The result will be count after finishing algorithm.

However, I approach with different idea. The following is algorithm of my idea:

- Break all time range into 2 parts: (time=start_time, type=start) and (time=end_time, type=end)
- Sort all that events. If time equals, prefer type=end.
- Go from that sorted events, if type = start: count++. else count --


count will be the total machine we need.

My question is: is there any wrong with my approach.

Thanks

There is one distinction of your algorithm, If time equals, prefer type=end. It turns out this specification is unnecessarily restrictive in the sense that you can break any tie that consists of requests of the same starting time arbitrarily. On first look, it might sound surprising that the algorithm still works when ties are breaking arbitrarily. One might take for granted that scheduling the one request that ends early should yield more room for later scheduling. However, it does not matter which one to schedule out of the requests of the same staring time. I will leave this little enigma as an exercise for readers to ponder and prove.
By the way, there are some sloppiness in the question and the algorithm. In the problem statement, it does not mention explicitly that each request must use one and only one resource all the way from its start time to its end time. That each request can use any resource. It does not specify whether a request that starts at time $$t_0$$ can use the same resource used by another request that ends at $$t_0$$, that is, whether those two requests are overlapping at $$t_0$$. The "total machine" is used suddenly near the end of the question, which should be, for the sake of consistency, "total number of resources". This short answer is written in the hope that all those ambiguities and sloppiness do not affect the high-level thinking by readers.