Start learning free

LESSON 328 OF 347 · GREEDY

Non Overlapping Intervals in C#: Greedy Sort by End Point, O(n log n)

Practice O(n log n) Read the full explanation

Given a collection of intervals, find the maximum number of non-overlapping intervals you can select.


Example 1:

Input: [[1,2],[2,3],[3,4],[1,3]]
Output: 3
Explanation: [1,2], [2, 3] and [3, 4] are non-overlapping.

Note:

  1. You may assume the interval's end point is always bigger than its start point.
  2. Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.

Your algorithm should run in O(n log n) time and use O(1) extra space.


STEP 1 OF 6
    Ctrl + Enter to check

    C# · GREEDY

    Non Overlapping Intervals in C#, explained

    Problem overview

    The method NonOverlappingIntervals(int[,] intervals) receives intervals as rows of a two-dimensional array: column 0 holds the start and column 1 the end. It returns the largest number of intervals you can select so that no two of them overlap. Intervals that only touch at an end point, like [1, 2] and [2, 3], do not overlap. Each end is larger than its start.

    For the intervals [1, 2], [2, 3], [3, 4] and [1, 3] the answer is 3: take the first three and skip [1, 3], which overlaps both [1, 2] and [2, 3].

    Approach: always take the interval that finishes first

    Checking every subset of intervals is exponential. A greedy rule is enough: sort the intervals by end point, then walk through them and take each one that starts no earlier than the end of the last one taken.

    Why does finishing first matter? The interval that ends earliest leaves the most room for the intervals after it. Suppose some best selection does not contain that interval. Its first interval ends no earlier, so swapping the earliest-ending interval in for it cannot create an overlap and keeps the count the same. Repeating the argument shows the greedy choices are never worse than any other plan.

    On the example, the sorted order by end is [1, 2], then the two intervals ending at 3, then [3, 4]. The scan takes [1, 2]. A candidate ending at 3 that starts at 2 is taken, since 2 is at least 2, and then [1, 3] is skipped because it starts at 1, before the last end of 3. Finally [3, 4] starts at 3 and is taken. The total is 3, whichever order the two tied intervals come in.

    Step by step

    1. Sort row indexes, not rows. C# cannot reorder the rows of an int[,] directly. Instead, store intervals.GetLength(0) in rows, create an int[] order holding 0, 1, ..., rows - 1, and sort it with Array.Sort and a comparison lambda that compares the end points of the two rows: intervals[first, 1] - intervals[second, 1].
    2. Take the first interval. Set result to 1 and lastTaken to order[0], the row that ends first. The conditional rows > 0 ? order[0] : 0 avoids reading order[0] from an empty array.
    3. Loop over the rest of order from position 1.
    4. Compare. The current interval is row order[i]. If its start, intervals[order[i], 0], is at least the end of the last taken one, intervals[lastTaken, 1], there is no overlap. The comparison uses >= because touching ends are allowed.
    5. Take it. Increment result and set lastTaken to order[i]. Store the row number, not the position in order, since the next comparison reads intervals[lastTaken, 1].
    6. Return result after the loop.

    The solution in C#

    class Solution {

    public int NonOverlappingIntervals(int[,] intervals) {
        int rows = intervals.GetLength(0);
        int[] order = new int[rows];
        for (int i = 0; i < rows; i++) order[i] = i;
        Array.Sort(order, (first, second) => intervals[first, 1] - intervals[second, 1]);
        int result = 1, lastTaken = rows > 0 ? order[0] : 0;
        for (int i = 1; i < rows; i++) {
            if (intervals[order[i], 0] >= intervals[lastTaken, 1]) {
                result++;
                lastTaken = order[i];
            }
        }
        return result;
    }
}

    C# details:

    • Sorting indirectly. A rectangular array is a single block, so you cannot swap its rows as objects. Sorting an array of row numbers gets the same effect, and intervals[order[i], 0] reads through that order.
    • The comparison lambda. Array.Sort(array, comparison) accepts a Comparison<int>. Returning a negative number means the first argument goes before the second, zero means a tie, and a positive number means it goes after. Subtraction is a compact way to produce that.
    • Subtraction can overflow. For ordinary values it is fine. If end points could be near int.MinValue and int.MaxValue, the difference would wrap and flip the sign. intervals[first, 1].CompareTo(intervals[second, 1]) avoids that.
    • Two variables, one declaration. int result = 1, lastTaken = ...; declares both as int.
    • Ties. Array.Sort is not a stable sort, so equal end points may come in either order. That does not change the count here.

    Complexity

    Time: O(n log n). The sort dominates. The scan afterwards is a single O(n) pass.

    Space: O(n) extra in this C# version, for the order array of row numbers. That array is the price of sorting rows of an int[,] without copying the data.

    Edge cases and common mistakes

    • Touching intervals. [1, 2] and [2, 3] are compatible. Using > instead of >= would reject them and return 1 for that pair.
    • Sorting by start instead of end. For [1, 5], [2, 3] and [4, 6], taking the earliest start picks [1, 5] and blocks both of the others, giving 1. Sorting by end gives 2.
    • Nested intervals. A long interval containing short ones is skipped automatically, because short ones end sooner and are taken first.
    • Storing the wrong index. Setting lastTaken = i stores a position in order, but the code reads it as a row of intervals. It would compare with the wrong interval.
    • Empty input. The guard stops the code from reading order[0], but result starts at 1, so zero intervals would still return 1. The expected answer is 0 for that case, so a program that must handle empty input needs an early return 0.
    • Thinking in terms of .Length. On a 2D array it counts every cell, so for 4 intervals it is 8. Use GetLength(0).

    Testing

    • [[1, 2], [2, 3], [3, 4], [1, 3]] gives 3.
    • [[1, 5], [2, 3], [4, 6]] gives 2.
    • [[1, 2], [2, 3]] gives 2.
    • [[1, 10], [2, 3], [3, 4], [4, 5]] gives 3.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free