Interval Problems and Sweep Line: Overlapping Ranges, Merge Intervals, Monotonic Stack and Calendar/Slot Scenarios

Version note: The code in this post was built with .NET 10 and C# 14 and verified with xUnit v3 4.0.2 tests; measurements were taken with BenchmarkDotNet 0.15.8.

Guess First

Bookstore, the online bookstore used as the shared example across this site's series, enters campaigns in the back office with "first day" and "last day" fields. Marketing has defined two campaigns: "Autumn Classics" from 1 to 10 November and "Black Friday" from 10 to 20 November. The code stores these dates as Start and End, checks "do the two intervals overlap?" and answers "no overlap". Is it right?

Second question: a courier has booked six delivery appointments on the same day: 09:00–11:00, 09:30–10:30, 10:00–12:00, 10:30–11:30, 11:00–13:00 and 14:00–16:00. How many vans are needed, at minimum, to serve them?

The Half-Open Interval: [Start, End)

Half of all interval problems are about the definition of the interval, not the algorithm. All the code in this post follows one rule: Start belongs to the interval, End does not.

// Half-open [Start, End): Start belongs to the interval, End does not
public readonly record struct Interval<T>(T Start, T End) where T : IComparable<T>
{
    public bool IsEmpty => Start.CompareTo(End) >= 0;

    public bool Overlaps(Interval<T> other) =>
        Start.CompareTo(other.End) < 0 && other.Start.CompareTo(End) < 0;

    public bool Contains(T point) => Start.CompareTo(point) <= 0 && point.CompareTo(End) < 0;
}

Two intervals overlap if each starts before the other ends; the one-line Overlaps covers every case (nested, partial, identical). The benefit of half-open intervals is that consecutive intervals line up cleanly: 09:00–10:00 and 10:00–11:00 do not overlap, 10:00 belongs to exactly one of them, and the duration is simply End - Start. We used the same discipline for effective-dated records in the Solution Patterns series post "Temporal Data: Effective-Dated Records, Price History and the Bitemporal Model".

Back to the opening campaigns. The form's "last day" is an inclusive value; using it directly as End loses a day:

Interval<DateOnly>[] wrong = [.. typed.Select(c => new Interval<DateOnly>(c.First, c.Last))];
Interval<DateOnly>[] halfOpen = [.. typed.Select(c => new Interval<DateOnly>(c.First, c.Last.AddDays(1)))];

End = last day:     Autumn Classics active on 2026-11-10? False, overlap: none
End = last day + 1: Autumn Classics active on 2026-11-10? True, overlap: [2026-11-01, 2026-11-11) and [2026-11-10, 2026-11-21)

The wrong conversion produces two bugs at once: the campaign does not appear active on its last day, and a real overlap is hidden. On 10 November both campaigns are active; whether the discounts should stack is a business-rule question, but first the code has to see the overlap. The answer to the opening question: the code is not right. The rule is simple: show the inclusive last day to the user, keep the data half-open, and convert at the boundary in exactly one place.

Sorting, Merging and Finding Overlaps

Comparing n intervals pairwise is O(n²). If we sort by start, an overlap can only begin between neighbours:

// Sort by start, then extend the last merged interval while the next one overlaps (or touches)
public static List<Interval<T>> Merge<T>(IEnumerable<Interval<T>> intervals, bool mergeTouching = true)
    where T : IComparable<T>
{
    List<Interval<T>> sorted = [.. intervals.Where(i => !i.IsEmpty).OrderBy(i => i.Start)];
    List<Interval<T>> merged = [];
    foreach (Interval<T> current in sorted)
    {
        if (merged.Count > 0)
        {
            Interval<T> last = merged[^1];
            int cmp = current.Start.CompareTo(last.End);
            if (cmp < 0 || (cmp == 0 && mergeTouching))
            {
                if (current.End.CompareTo(last.End) > 0) merged[^1] = last with { End = current.End };
                continue;
            }
        }

        merged.Add(current);
    }

    return merged;
}

The cost comes from sorting: O(n log n), and the merge loop is O(n). Two details matter. First, current.End is not always greater than last.End; [2, 3) can sit inside [1, 10), and we must not shrink the last interval. Second, whether to merge touching intervals depends on context: when computing a staff member's busy hours, 09–10 and 10–11 are one block; when reporting two separate campaigns, they should stay apart. Both cases are pinned down in the tests for [8, 10), [10, 12).

The same idea is enough to find an overlap, with one difference: we must remember the interval that reaches furthest so far (reach), not the neighbour. In the order [1, 10), [2, 3), [4, 5), the interval that overlaps [4, 5) is not its neighbour [2, 3) but [1, 10). The FindOverlap_LongIntervalCoversLaterOne_FindsIt test exists for this case.

Sweep Line: How Many at Most at the Same Time?

The second question is different: not which intervals overlap, but how many intervals are open at any moment. The sweep line technique splits every interval into two events: +1 at the start, −1 at the end. Sort the events by time, walk them left to right, and the counter gives the number of intervals open at that moment:

// Sweep line: +1 at every start, -1 at every end; at equal times the end comes first (half-open)
public static (int Max, T At) MaxConcurrent<T>(IEnumerable<Interval<T>> intervals) where T : IComparable<T>
{
    List<(T Time, int Delta)> events = [];
    foreach (Interval<T> i in intervals)
    {
        events.Add((i.Start, +1));
        events.Add((i.End, -1));
    }

    events.Sort((a, b) =>
    {
        int c = a.Time.CompareTo(b.Time);
        return c != 0 ? c : a.Delta.CompareTo(b.Delta); // -1 before +1
    });

    int current = 0, max = 0;
    T at = default!;
    foreach ((T time, int delta) in events)
    {
        current += delta;
        if (current > max)
        {
            max = current;
            at = time;
        }
    }

    return (max, at);
}

vans needed: 3 (from 10:00)

The answer is 3: at 10:00 the 09:00, 09:30 and 10:00 appointments are open at the same time. At 10:30 one ends and one starts, and the same happens at 11:00; without the "end first" rule in the sort, the 09:00–11:00 appointment would still count as open at 11:00 and the result would wrongly be 4. In the twentieth post of this series we solved the same problem for the number of meeting rooms with a min-heap of end times; the sweep line gives the same answer with a simpler structure and also tells you when the peak happens. The cost is O(n log n) again.

All these functions are offline algorithms that process the interval list once. If intervals keep being added and each time you ask "which bookings overlap this interval?", you need an interval tree: a balanced BST, as in the twelfth post of this series, where every node also stores the largest End in its subtree. Inserting and finding an overlap become O(log n). The BCL has no ready-made interval tree; in most backend applications the database answers this question.

Finding Gaps: Warehouse Shifts

The warehouse is open 06:00–22:00 and the shifts are 06–14, 13–20 and 08–12. The hours nobody covers are what remains when you subtract the merged shifts from the opening hours:

// Gaps inside [window.Start, window.End) not covered by any busy interval
public static List<Interval<T>> Gaps<T>(Interval<T> window, IEnumerable<Interval<T>> busy) where T : IComparable<T>
{
    List<Interval<T>> gaps = [];
    T cursor = window.Start;
    foreach (Interval<T> b in Merge(busy))
    {
        if (b.End.CompareTo(window.Start) <= 0 || b.Start.CompareTo(window.End) >= 0) continue;
        if (b.Start.CompareTo(cursor) > 0) gaps.Add(new Interval<T>(cursor, b.Start));
        if (b.End.CompareTo(cursor) > 0) cursor = b.End;
    }

    if (cursor.CompareTo(window.End) < 0) gaps.Add(new Interval<T>(cursor, window.End));
    return gaps;
}

uncovered: 20:00-22:00

The same function answers "which delivery slots should we show the customer?": the gaps in the courier's busy hours that are longer than the requested duration. We used TimeOnly here because a shift is not tied to a date; a shift that crosses midnight (22:00–06:00) cannot be expressed with TimeOnly, so you either split it into two intervals or use DateTimeOffset.

Monotonic Deque: The Lowest Price of the Last 30 Days

In the fourth post of this series we solved "next greater element" and the stock span problem with a monotonic stack. The two-ended version of the same idea is useful for sliding window problems. The European Union's price indication directive (98/6/EC, Article 6a, added by Directive 2019/2161) requires a price reduction announcement to show, as the prior price, the lowest price applied during at least the 30 days before the reduction. Bookstore needs to know "the lowest price of the last 30 days" for every book on every day.

// Monotonic deque of indexes: values increase from front to back, the front is the window minimum. O(n) in total
public static decimal[] Minimums(IReadOnlyList<decimal> values, int window)
{
    ArgumentOutOfRangeException.ThrowIfLessThan(window, 1);
    decimal[] result = new decimal[values.Count];
    int[] deque = new int[values.Count];
    int head = 0, tail = 0; // deque holds deque[head..tail)
    for (int i = 0; i < values.Count; i++)
    {
        while (tail > head && values[deque[tail - 1]] >= values[i]) tail--; // can never be a minimum again
        deque[tail++] = i;
        if (deque[head] <= i - window) head++; // fell out of the window on the left
        result[i] = values[deque[head]];
    }

    return result;
}

When a new price arrives, we drop the older prices that are greater than or equal to it from the back: the new price is smaller and will stay in the window longer, so they can never be the minimum again. If the index at the front has left the window, we drop it from the front. Every index enters the deque once and leaves at most once, so the total is O(n); the naive version scans the window for every day, O(n·k). We kept the deque in an array of length n with two indexes; since every index enters at most once, there is no need to wrap around like the ring buffer in the fourth post. The BCL has no general-purpose deque collection; LinkedList<T> works at both ends but allocates for every element.

day 13: price    15, lowest of last 30 days    15
day 39: price    20, lowest of last 30 days    15
day 43: price    24, lowest of last 30 days    20
day 54: price    24, lowest of last 30 days    20
discount on day 55: new price 18, yesterday 24 (25 % off), prior price 20 (10 % off)

In the scenario the book costs 20 TL; 42 to 45 days before the discount day it had a short sale at 15 TL, then it was raised to 24 TL for 15 days. When it drops to 18 TL on day 55, saying "it was 24 yesterday, 25 percent off" is tempting; but the lowest price of the previous 30 days is 20, so the reduction you can announce is 10 percent. Raising the price briefly and then "discounting" it is exactly what this rule is meant to prevent. The measurement, on a price series of 100,000 days:

| Method         | Window | Mean        | Ratio | Allocated |
|--------------- |------- |------------:|------:|----------:|
| Naive          | 30     |  5,733.6 us |  1.00 |   1.53 MB |
| MonotonicDeque | 30     |    877.6 us |  0.15 |   1.91 MB |
|                |        |             |       |           |
| Naive          | 365    | 48,350.4 us |  1.00 |   1.53 MB |
| MonotonicDeque | 365    |    885.6 us |  0.02 |   1.91 MB |

Absolute times depend on the machine; look at the ratios. When the window grows from 30 to 365, the naive version gets 8.4 times slower, while the deque version's time does not change: the window size does not enter the cost. The price is the extra int[] allocated for the indexes.

Time Zones: Not Counting the Same Day Twice

When interval endpoints are DateTimeOffset values there is one more problem: whose day is "the day"? I grouped three deliveries by UTC date and by local date in Istanbul:

TimeZoneInfo istanbul = TimeZoneInfo.FindSystemTimeZoneById("Europe/Istanbul");
DateTimeOffset[] deliveredUtc =
[
    new(2026, 11, 15, 20, 45, 0, TimeSpan.Zero),
    new(2026, 11, 15, 22, 30, 0, TimeSpan.Zero),
    new(2026, 11, 16, 7, 15, 0, TimeSpan.Zero),
];

by UTC date   2026-11-15: 2
by UTC date   2026-11-16: 1
by local date 2026-11-15: 1
by local date 2026-11-16: 2

22:30 UTC is 01:30 the next day in Istanbul. If the daily courier report is computed in UTC and the warehouse shift plan in local time, the same delivery falls on different days in the two reports, and someone who combines the two reports counts it twice. The rule is the one from the Solution Patterns series post "Time and Time Zones: UTC Instants, Local Business Dates, DateOnly and TimeProvider": store the instant in UTC, and convert it to a business date as a DateOnly using a single time zone, in a single place.

In Production

Let the database protect against overlaps too. A check in application code lets both of two concurrent requests through: both read, both see "free", both write. PostgreSQL prevents this at the data level with an exclusion constraint. The definition below follows the examples in PostgreSQL's range type and btree_gist documentation. This section is based on the official documentation.

CREATE EXTENSION IF NOT EXISTS btree_gist;

CREATE TABLE delivery_slot_booking (
    van_id int       NOT NULL,
    slot   tstzrange NOT NULL,
    EXCLUDE USING gist (van_id WITH =, slot WITH &&)
);

The default bounds of tstzrange are '[)', that is, half-open; two back-to-back slots do not count as overlapping. Two overlapping slots for the same van, however, are rejected on the second INSERT. Bookstore's database is SQL Server, and SQL Server has no exclusion constraint; there you have to do the check in a serializable transaction that locks the van's rows, or split slots into fixed pieces (say 30 minutes) and use a unique index.

Test the boundary values. All the bugs are at the edges: intervals that end and start at the same time, single-day, zero-length and nested intervals. Every case in the tests corresponds to a bug.

Sort a large list once. If there are hundreds of queries for the same day, keep the bookings sorted instead of sorting them every time, or leave the query to the database.

Common Pitfalls

Off-by-one with closed intervals. Using the "last day" field directly as End loses the last day and hides overlaps. Conversely, forgetting to subtract a day when showing half-open data as "until 10 November" shows the user the wrong date.

Not thinking about the order of simultaneous events. If the sweep line does not process ends before starts, back-to-back appointments count as overlapping and you plan an extra van.

Updating End blindly in a merge. If you write merged[^1] = last with { End = current.End } unconditionally, a nested interval shortens the last interval; merging [1, 10) and [2, 3) gives [1, 3).

Mixing time zones. Using the UTC date in one place and the local date in another within the same flow puts a delivery on two different days. Convert the date in one place, with one time zone.

A Small Experiment

★☆☆ Using Gaps, write a method that returns "free delivery slots of at least 90 minutes" and pin down the result for a 09:00–18:00 window and the opening appointments with a test.

★★☆ Extend MaxConcurrent to return not only the moment the peak starts but the interval it lasts (such as [10:00, 10:30)). If there are several peak intervals, return them all.

★★★ Write a Gaps that supports shifts crossing midnight (22:00–06:00): take the input as TimeOnly intervals, split them in two when needed, find the gaps in a 7-day weekly plan with DateTimeOffset, and report them in the Europe/Istanbul time zone.

With intervals we computed exact answers. In the next post we give up exactness on purpose: Bloom filter, Count-Min Sketch and HyperLogLog give approximate but controlled answers, using a few kilobytes, to "has this e-mail been seen before", "which books are viewed most" and "how many unique visitors came today".