algorithm - Finding maximal set of disjoint intervals - Priority to longer intervals

Question

A maximal set of disjoint intervals is a standard algorithm question.

Basically given a set of overlapping intervals, (1,2),(2,6),(1,10),(6,13), we can choose (1,2),(2,6),(6,13). The standard algorithm sorts the lists of intervals by the second element in each interval and proceeds to choose the intervals in a greedy manner. Because we already have a list in increasing order of the second element, it ensures we maximize the number of intervals.

Now, this question has been modified to give priority to longer intervals. For example, given a list (1,2),(2,6),(1,10),(6,13), we'll choose the interval (1,10) and not the one we chose above.

Another example: (1,5),(2,7),(11,18), the answer in the modified question would be (2,7),(11,18) against (1,5),(11,18) we would get by proceeding in a greedy manner.

I need some help in modifying the original algorithm to fit the second question.

Thank you.

Reference: https://www.geeksforgeeks.org/maximal-disjoint-intervals/

question from:https://stackoverflow.com/questions/65875416/finding-maximal-set-of-disjoint-intervals-priority-to-longer-intervals

Answer 1

Waitting for answers