One solution which is world known is to use greedy approach. Is there any other approach we can use to remove the O(n*log n) factor? In other words, can we do it without sorting them in monotonically increasing order of finish time?
Are you asking whether the activity selection problem can be solved in O(n) time by removing the sorting step? If such an algorithm were known then it would be published and widely known. Further, I find it unlikely that such an algorithm exists. This is a great problem for teaching greedy algorithms because the algorithm is so simple yet so many other simple greedy approaches work in many cases but fail in general. If you try to resolve conflicts without sorting then you generally end up with an O(n^2) running time by adding extra comparisons or storing too many possibilities.
That being said, I would be happy to be proved wrong here. In addition, there is an alternative (although functionally equivalent) approach: sort by monotonically decreasing start times and select backwards rather than forward. I assume that is not what you intended, however.
Thank you so much for the response Cris. Yes I am talking about reducing its running time to O(n). I was thinking of mapping this problem to the graph coloring problem and see if it the running time can be reduced to at least O(n log n).
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms