Start learning free

LESSON 349 OF 410 · GREEDY

Non Overlapping Intervals in Java: Greedy 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. Apart from the sorting, the greedy pass needs only O(1) extra space.


STEP 1 OF 6
    Ctrl + Enter to check

    JAVA · GREEDY

    Non Overlapping Intervals in Java, explained

    Problem overview

    The method nonOverlappingIntervals receives an int[][] named intervals, where each row {start, end} is one interval. It returns the largest number of intervals that can be chosen so that no two chosen intervals overlap. Intervals that only touch, such as [1, 2] and [2, 3], do not overlap. Each end point is greater than its start point.

    For [[1, 2], [2, 3], [3, 4], [1, 3]] the answer is 3: the intervals [1, 2], [2, 3] and [3, 4] fit one after another, and [1, 3] overlaps two of them. No choice of four works, since [1, 3] overlaps [1, 2] and [2, 3].

    This is the classic activity selection problem: think of each interval as a meeting that needs a room, and ask for the most meetings that fit in one room. A closely related version asks for the fewest intervals to remove so that the rest do not overlap. That number is intervals.length minus the answer computed here.

    Approach: always take the interval that ends first

    Trying every subset of intervals would take O(2^n) time, and a dynamic programming solution that compares each interval with all earlier ones takes O(n^2). The task asks for O(n log n), which a greedy strategy reaches. A greedy algorithm builds the answer by making the best local choice at each step and never reconsidering it. Here the right local choice is the question: which interval should I take first?

    The one that ends earliest. An early end leaves the largest possible stretch of time for everything that comes after. Suppose an optimal answer starts with some other interval. Swap that interval for the one with the earliest end. The earliest-ending interval finishes no later than the one it replaces, so it cannot overlap anything that the original choice left room for, and the count stays the same. So some optimal answer always contains the earliest-ending interval, and the same argument applies to what remains after it.

    Two other greedy ideas look attractive but fail. Taking the earliest start picks [1, 10] from [[1, 10], [2, 3], [4, 5], [6, 7]] and then nothing else fits, giving 1 where the answer is 3. Taking the shortest interval first can also go wrong, since one short interval may sit in the middle of two long ones that would otherwise both fit.

    In the algorithm, sort the intervals by end point, take the first one, and then scan from left to right. Take an interval whenever it starts at or after the end of the last one taken. Skip it otherwise.

    On the example, sorting by end gives [1, 2], [2, 3], [1, 3], [3, 4]. Take [1, 2]. Next [2, 3] starts at 2, which is at least the last end of 2, so take it. [1, 3] starts at 1, before the last end of 3, so skip it. [3, 4] starts at 3, which is at least 3, so take it. The result is 3.

    Step by step

    1. Sort by end point. Arrays.sort needs a comparator, because an int[] has no natural order. The lambda receives two intervals, first and second, and returns first[1] - second[1], which is negative when first ends earlier.
    2. Take the first interval. After sorting it ends the earliest, so taking it is always safe. Start result at 1 and remember its index in lastTaken, which starts at 0. Storing the index lets the next comparison read the end point from the array.
    3. Loop over the rest. The index i goes from 1 up to intervals.length - 1, since index 0 is already taken.
    4. Test for a gap. If intervals[i][0] >= intervals[lastTaken][1], the current interval starts when or after the last one ends, so they do not overlap. The >= is what lets touching intervals count as separate.
    5. Take it. Increment result and set lastTaken to i.
    6. Return result after the loop.

    The solution in Java

    class Solution {

    public int nonOverlappingIntervals(int[][] intervals) {
        Arrays.sort(intervals, (first, second) -> first[1] - second[1]);
        int result = 1, lastTaken = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= intervals[lastTaken][1]) {
                result++;
                lastTaken = i;
            }
        }
        return result;
    }
}

    Java details to know:

    • The import. Arrays lives in java.util, so a file of your own needs import java.util.Arrays;.
    • Sorting an array of arrays. intervals is an array of int[] objects, so Arrays.sort accepts a comparator, which it would not for a plain int[]. The sort moves the row references and does not copy the numbers.
    • The input is modified. The sort is in place, so the caller's array ends up reordered. Work on a copy if the original order matters.
    • The comparator and overflow. The subtraction first[1] - second[1] overflows int when the end points are far apart, such as 2,000,000,000 and -2,000,000,000. The wrapped result has the wrong sign and breaks the sort. For example, with {{1, 2000000000}, {-2147483648, -2000000000}} the code above returns 1 instead of 2. Integer.compare(first[1], second[1]) never overflows and is the safer way to write the same comparison.

    Complexity

    Sorting takes O(n log n) comparisons and the single pass afterwards takes O(n), so the total is O(n log n). The pass itself uses only three int variables. The sort of object arrays in Java is a merge-based sort that can use extra memory, so the strict extra space is O(n) in the worst case, even though the scan is O(1).

    Edge cases and common mistakes

    • Using > instead of >=. Then touching intervals are treated as overlapping and the example returns 2.
    • Sorting by start point. The scan then compares with the wrong interval, and the result can be too small, as the [1, 10] example above shows.
    • Identical intervals. [[1, 2], [1, 2], [1, 2]] returns 1. The copies overlap each other completely.
    • Nested intervals. In [[1, 10], [2, 3], [4, 5], [6, 7]] the short ones that end first win, and the answer is 3.
    • Empty input. The method starts result at 1, so an empty array returns 1 instead of 0. The task implies at least one interval; add a check for intervals.length == 0 if empty input is possible.

    Testing

    Try [[1, 2], [2, 3], [3, 4], [1, 3]] (3), [[1, 2], [1, 2], [1, 2]] (1), [[1, 10], [2, 3], [4, 5], [6, 7]] (3) and [[1, 2], [1, 3]] (1).

    Keep going with JavaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free