3
$\begingroup$

This question already has an answer here:

This is an interview question.
Suppose you have an array of n segments, when each segment is a pair of two integers: start point and end point. For example: (1,3).

Two segments s1,s2 are intersecting if
(s2.start<=s1.start<=s2.end) or (s1.start<=s2.start<=s1.end)
For example: (1,3),(2,4) are intersecting.

Find an algorithm for finding maximum number of segments in the array (and returning those segments in some list) which don't intersect.

My attempt: I thought maybe some sorting can help, but didn't find how so tried something else. Then the interviewer gave me a hint: the run time expected is O(nlogn).

So now I'm sure the solution need to involve some sorting algorithm, but I don't know how to use it.

Any suggestions?

$\endgroup$

marked as duplicate by Apass.Jack, David Richerby, Thinh D. Nguyen, xskxzr, Evil Nov 1 '18 at 15:13

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ This problem, also called "activity selection problem", is explained in great detail in CLRS as its very first example in chapter "Greedy algorithms". $\endgroup$ – Apass.Jack Oct 31 '18 at 18:45
4
$\begingroup$

I can show you a solution that I suspect is $O(n \log n)$, but I haven't proven the runtime. Edit: Following a linked solution, I amended this solution to be simpler and run in $O(n \log n)$.

So the issue is that if you take a greedy approach, you might choose a 'bad' segment that blocks a favorable choice later. That is, choices you make at the beginning affect what choices you have available later on. This suggests a dynamic programming approach.

First step is to sort the segments by their start times. Then, you need to define exactly what you're going to calculate. We'll define $numsegs(i)$ as the max number of segments possible when segment $i$ is included and has the earliest start time of all included segments.

Then your final answer is going to be the maximum of value of $numsegs(i)$ for all possible values of $i$. Now you need a formula for $numsegs(i)$.

Think about how to calculate $numsegs(0)$, the maximum segment count when you include the first segment. If we include the first segment, then we can only include other segments that begin after the first segment ends. So we need to find the index of the first segment that is compatible with segment 0. We can do this in $O(\log n)$ time with a simple binary search - let that index be $k$. Now, we can say that $numsegs(0)$ is 1 (for segment 0) plus the maximum of $numsegs(k), numsegs(k+1), \dots, numsegs(n)$. (There's an edge case to consider as well. If segment $i$ doesn't have any compatible segments after it, then $numsegs(i)$ is just 1.)

You can compute $numsegs(i)$ in a very similar way. Note that $numsegs(i)$ depends only on $numsegs$ values greater than $i$. Therefore we can compute $numsegs(n-1)$ first, then $numsegs(n-2)$, and so on, caching the values as we go, and we'll never have to recalculate any $numsegs$ values.

This solution is actually $O(n^2)$. To compute $numsegs(i)$, you have to find the maximum among potentially $n-i$ following $numsegs$ values. How then to get the total runtime down to $O(n \log n)$?

Edit: As a linked solution pointed out, we can compute the maximum quickly using caching. Suppose we want to know the maximum $numsegs$ value starting from index $k$. We can just compare $numsegs(k)$ to the maximum starting from $numsegs(k+1)$, which we cached in a previous step.

$\endgroup$
  • $\begingroup$ Sorry, but your algorithm is wrong as your "first step is to sort the segments by their start times". Start times are irrelevant in this problem. Only their finishing times/end points are relevant. $\endgroup$ – Apass.Jack Oct 31 '18 at 18:37
  • $\begingroup$ I think it's actually correct. Note that this is a DP solution, not the typical earliest-finish greedy approach (and start times do matter for earliest-finish, of course - you just don't sort on them at the beginning). More importantly, though, any interval scheduling algorithms based on end times could be rewritten to be based on start times. We don't care which 'direction time goes' - all we care about is which intervals overlap, which is the same forward and backward. $\endgroup$ – ConcernedCitizen Oct 31 '18 at 22:36
  • $\begingroup$ Now I see. Your approach is the exact mirror of the approach in the first answer to the linked question. That answer starts calculation from the interval that ends earliest while your answer starts calculation from the interval that starts latest. Put it in another way, if the start point and the end point of the each interval is switched, your approach becomes the approach in that answer. So your answer is correct. $\endgroup$ – Apass.Jack Nov 1 '18 at 1:47

Not the answer you're looking for? Browse other questions tagged or ask your own question.