You have $n$ events on your calendar, defined as intervals with a start time $s_i$ and a finish time $f_i$. The events might overlap, and you want to attend all the events, so you are going to create $k$ clones of yourself to achieve this. You want to minimize the number of clones you need, $k$. A clone can attend a certain non-overlapping subset of events.

Source: https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/151160c7c18d3f87159b7482823ff61c_MIT6_046JS15_Recitation6.pdf

I am trying to solve the problem above. The solution in the pdf, sorts the starting times. However, I think and have proved (by showing that an optimal solution can go through a series of swaps so that it becomes the result of the wanted algorithm) that it can be done by sorting the ending times. Basically, the algorithm is:

  1. Sort the ending times.
  2. Pop the interval with the smallest ending time. If it can't be visited by any of the existing clones, then make a new clone. Otherwise, choose the clone with the largest ending time such that the interval can still be taken by that clone.

I am pretty convinced that this works, however, I am not able to find any reference on the internet about this algorithm.

Sorting by $f_i$ is optimal in another problem of finding the maximum number of events one can take but not optimal by $s_i$ so it is intuitive to extend the reasoning to this problem. Is this conceptual approach correct?

  • $\begingroup$ What is your question? $\endgroup$
    – orlp
    Commented Feb 20 at 12:20
  • $\begingroup$ @orlp I am looking for a reference or verification that it is valid. $\endgroup$
    – Lipid
    Commented Feb 20 at 12:23
  • 2
    $\begingroup$ That is still not a question. A question ends with a question mark, e.g. "Is this correct?". Please edit your post to include a question so people can answer it. $\endgroup$
    – orlp
    Commented Feb 20 at 12:25
  • $\begingroup$ Please consult cs.stackexchange.com/q/59964/755 and follow the guidance there. $\endgroup$
    – D.W.
    Commented Feb 20 at 17:58
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    Commented Feb 20 at 17:58


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.