Can interval partition solve by sort by different approach

Question

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

Answer 1

Yes, your approach is correct.

"The interval partitioning problem" is more commonly known as "the interval-graph coloring problem". It is problem 16.1-4 in the book Introduction to Algorithm by CLRS, third edition.

The idea behind the common solution described in the question and your approach is essentially the same. Arguably, your algorithm is simpler than that solution given by many sources. On the other hand, there are many sources that give the roughly the same algorithm as yours such as the article at GeeksForGeeks.

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.