1
$\begingroup$

I'm trying to create an algorithm in C# that given a list of ranges (segments) it produces a compacted list of them:

Example 1

Input: [1, 3], [2, 6]

Output: [1, 6]

Example 2

Input: [1, 2], [2, 3]

Output: [1, 3]

Example 3

Input: [1, 2], [4, 6], [2,4]

Output: [1, 6]

Too visualize the problem better, this problem is similar to this: if you have a shop that opens from Monday to Tuesday and from Tuesday to Sunday, then you can say that your shop opens from Monday to Sunday. This is what the algorithm should do: to simplify the ranges and give the minimum set of merged ranges.

I'm absolutely lost on how to approach this problem. Thanks in advance.

$\endgroup$
  • 2
    $\begingroup$ It seems I have misread the first example. I suppose you want the smallest list of ranges such that the set of points inside the ranges is the same as your input. In your examples, this is always a single range. Is this always true for the inputs you receive, or is e.g. [1,3] [2,4] [6,7] a possible input? $\endgroup$ – Discrete lizard Apr 15 at 12:12
  • $\begingroup$ I do not understand what is the blocking point. Can't you just sort the ranges on the beginings and compare the end of each range with the begining of the following one ? $\endgroup$ – Vince Apr 15 at 12:13
  • $\begingroup$ @Vince: I think this can be made to work by tracking the "high-water mark" of ending points, i.e., the rightmost endpoint seen so far, and comparing with that instead of the beginning of the next interval. (Otherwise, IIUC, you would incorrectly report an endpoint at 10 for the interval list ((1, 15), (3, 10), (12, 20)).) $\endgroup$ – j_random_hacker Apr 15 at 12:30
  • 1
    $\begingroup$ @j_random_hacker you are totally right about that, I did not entered much in details. $\endgroup$ – Vince Apr 15 at 21:56
3
$\begingroup$
  1. Make a list of all $2n$ beginning and ending points of the $n$ ranges. Record each as a (position, type) pair.
  2. Sort this list by position, with starting points comparing below ending points when positions are equal.
  3. Loop through the sorted list, incrementing a counter variable (initially zero) whenever you see a beginning point and decrementing it whenever you see an ending point. On a 0->1 transition of this variable, output the current position as a starting point. On a 1->0 transition, output the current position as an ending point.
$\endgroup$
  • $\begingroup$ It is an interesting way to do it. I used something more simple in work like what I said in comment. When I saw this answer I thought it could speed up a lot my code that was more complex with several if statements, list modification... I was surprised that it was not the case (my coding may be unperfect), so I wonder if sorting $2n$ instead of $n$ could potentially make this version a little slower, even if it is a very nice way to treat analytically the problem. $\endgroup$ – Vince Apr 15 at 22:06
  • $\begingroup$ @Vince: I expect your way would be faster by a constant factor around 2 on large-enough inputs, because sorting typically involves lots of out-of-order memory accesses and my way sorts twice as many things as yours. But a lot depends on the language, implementation and hardware. $\endgroup$ – j_random_hacker Apr 16 at 11:05
  • $\begingroup$ @j_random_hacker I'm quite new to algoritms, sorry. I don't understand what $2n$ means. Can you, please, illustrate your answer with an example for dummies like me? Thanks in advance! $\endgroup$ – SuperJMN Apr 17 at 10:23
  • $\begingroup$ I'm calling the number of ranges $n$. $2n$ is just 2 times $n$. There will be $2n$ entries in the list to be sorted because there's a separate entry for the starting point and ending point of each range. Is that clearer? $\endgroup$ – j_random_hacker Apr 17 at 11:28
0
$\begingroup$

OK, thanks to @j_random_hacker, that gave me the idea of sorting the intervals by starting point, I have achieved what it seems is a correct way to implement the algorithm.

It's in C# and uses tuples. It's directly copied from a LINQ

void Main()
{
    var list = new[]{
        (1, 4),
        (4, 5),
        (8, 20),
        (19, 20),
        (7, 8),
    };

    var simplified = SimplifyIntervals(list);
    simplified.Dump();
}

public IEnumerable<(int, int)> SimplifyIntervals(IEnumerable<(int, int)> intervals)
{
    var ordered = intervals.OrderBy(x => x.Item1);
    var initialList = new List<(int, int)> { ordered.First() };
    var simplifiedIntervals = ordered.Aggregate(initialList, (previousList, candidate) =>
                {
                    var last = previousList.Last();
                    if (candidate.Item1 <= last.Item2)
                    {
                        var toAdd = (Math.Min(last.Item1, candidate.Item1), Math.Max(last.Item2, candidate.Item2));
                        return previousList.Take(previousList.Count() - 1).Concat(new[] { toAdd }).ToList();
                    }

                    return previousList.Concat(new[] { candidate }).ToList();
                });

    return simplifiedIntervals;
}

The results in with the list above throw these results:

enter image description here

$\endgroup$
  • 2
    $\begingroup$ Thanks, but a couple of things: Pseudocode is preferred to source code here, especially unusual source code (I don't know LINQ); My answer does not suggest sorting by starting points, so if that's what you meant and that's what your LINQ code is doing, you're doing something different than what I suggested (maybe closer to what Vince suggested in a comment?) $\endgroup$ – j_random_hacker Apr 17 at 11:34
  • $\begingroup$ We're not a coding site, so we discourage code-only answers. Instead, we're looking for ideas, algorithms, concise pseudocode, proofs of correctness, analysis of runtime, explanation, etc. Please edit your answer to explain the main ideas in some other way that a big block of code. $\endgroup$ – D.W. Apr 17 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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