4
\$\begingroup\$

We are given an array of intervals we need to merge all overlapping intervals and sort the resulting non-overlapping intervals. When they "touch" in a single point, intervals are also considered to be overlapping .

class Span
{
    public uint Start { get; }
    public uint End { get; }

    private Span(uint start, uint end)
    {
        Start = start;
        End = end;
    }

    private static Span _default = new Span(0, 0);

    // To avoid constructor throwing an exception
    public static Span Create(uint start, uint end)
    {
        if (start > end) throw new ArgumentOutOfRangeException(nameof(start), "Begin cannot me more than end");
        return new Span(start, end);
    }

    public bool IsOverlapped(Span other)
    {
        return Start <= other.End && End >= other.Start;
    }

    public Span Merge(Span other)
    {
        if (!IsOverlapped(other)) throw new ArgumentOutOfRangeException(nameof(other), "Spans must overlap");
        return new Span(Math.Min(Start, other.Start), Math.Max(End, other.End));
    }

    public bool TryMerge(Span other, out Span mergedItem)
    {
        mergedItem = _default;
        if (!IsOverlapped(other)) return false;
        mergedItem = new Span(Math.Min(Start, other.Start), Math.Max(End, other.End));
        return true;
    }
}

// In reality this method will be in a different class where it belongs
class Util
{
    public static Span[] Normalise(Span[] spans)
    {
        var results = new List<Span>();
        foreach (var item in spans.OrderBy(x => x.Start))
        {
            var lastResultIndex = results.Count - 1;
            if (lastResultIndex >= 0 && results[lastResultIndex].TryMerge(item, out Span mergedItem))
            {
                results[lastResultIndex] = mergedItem;
            }
            else
            {
                results.Add(item);
            }
        }
        return results.ToArray();
    }
}
\$\endgroup\$

1 Answer 1

0
\$\begingroup\$

I can't see the point in having the Create method here, there's no reason why a constructor can't throw an exception in C#. I'd just get rid of Create and move it all into the constructor (making it public).

The name IsOverlapped sounds a bit odd to me. Is is present tense and Overlapped is past tense. Maybe something like IsOverlapping or even just Overlaps.

You have a typo here: "Begin cannot me more than end". me should be be.

If you have access to expression-bodied members, they can reduce noise IMO:

public bool Overlaps(Span other) => other != null && Start <= other.End && End >= other.Start;

You'll notice that I've also put a null check for other in there at the same time.

You should rewrite Merge to call TryMerge internally:

public Span Merge(Span other) => 
    TryMerge(other, out var mergedSpan)
        ? mergedSpan
        : throw new ArgumentOutOfRangeException(nameof(other), "Spans must overlap");

I really value conciseness and I'm happy with throw expressions so I like this kind of pattern. If you don't, this version would also be fine:

public Span Merge(Span other)
{
    if (!TryMerge(other, out var mergedSpan))
        throw new ArgumentOutOfRangeException(nameof(other), "Spans must overlap");
    return mergedSpan;
}

Note: there's no need to check for null here as we now do that in Overlaps.

Your Normalise method looks good to me. It's a simple algorithm and easy to read.

\$\endgroup\$

Your Answer

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

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