Solving Merge Intervals

To see the question, click here.

Naive Approach

The idea is to use the concept of Merge Intervals and sort the intervals based on the start time. If the current interval overlaps the previous one, update the end time. If there is no overlap, add the previous interval to the result and update the start and end times. Add the last interval to the result.

// TC: O(n^2)
// SC: O(n)

import java.util.ArrayList;
import java.util.List;

class MergeIntervals {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0)
            return new int[0][0];

        List<int[]> result = new ArrayList<>();

        for (int i = 0; i < intervals.length; i++) {
            for (int j = i + 1; j < intervals.length; j++) {
                if (intervals[i][0] > intervals[j][0]) {
                    int[] temp = intervals[i];
                    intervals[i] = intervals[j];
                    intervals[j] = temp;
                }
            }
        }

        int start = intervals[0][0];
        int end = intervals[0][1];

        for (int i = 1; i < intervals.length; i++) {
            int[] curr = intervals[i];

            if (curr[0] <= end) {
                end = Math.max(end, curr[1]);
            } else {
                result.add(new int[] { start, end });
                start = curr[0];
                end = curr[1];
            }
        }

        result.add(new int[] { start, end });

        return result.toArray(new int[0][0]);
    }

    public static void main(String args[]) {
        MergeIntervals mi = new MergeIntervals();
        int[][] intervals = { { 1, 3 }, { 2, 6 }, { 8, 10 }, { 15, 18 } };
        int[][] result = mi.merge(intervals);
        for (int[] interval : result) {
            System.out.println(interval[0] + " " + interval[1]);
        }
    }
}

Performance

The time complexity of the merge method is O(n^2). We use the bubble sort algorithm to sort the intervals based on their start times. Then, we iterate through the sorted intervals once to merge overlapping intervals, which takes O(n) time. Overall, the time complexity is dominated by the sorting step. The space complexity is O(n). This is because we use a List to store the merged intervals, potentially containing all the intervals in the worst-case scenario where none overlap.

Refined Approach

Instead of using the bubble sort algorithm, we will utilize the sort method of Arrays class. Because the intervals are stored in a 2D array, direct use of the sort method is not possible. Instead, a custom comparator defined by a lambda expression is used.

Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

This comparator instructs the sort method to arrange the intervals based on their starting points in ascending order.

// TC: O(nlogn)
// SC: O(n)

import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

class MergeIntervals {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0)
            return new int[0][0];

        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        List<int[]> result = new ArrayList<>();

        int start = intervals[0][0];
        int end = intervals[0][1];

        for (int i = 1; i < intervals.length; i++) {
            int[] curr = intervals[i];

            if (curr[0] <= end) {
                end = Math.max(end, curr[1]);
            } else {
                result.add(new int[] { start, end });
                start = curr[0];
                end = curr[1];
            }
        }

        result.add(new int[] { start, end });

        return result.toArray(new int[0][0]);
    }

    public static void main(String args[]) {
        MergeIntervals mi = new MergeIntervals();
        int[][] intervals = { { 1, 3 }, { 2, 6 }, { 8, 10 }, { 15, 18 } };
        int[][] result = mi.merge(intervals);
        for (int[] interval : result) {
            System.out.println(interval[0] + " " + interval[1]);
        }
    }
}

Performance

The time complexity of the merge method is O(nlogn). This is because we first sort the intervals based on their start times which takes O(nlogn) time. Then we iterate through the sorted intervals once to merge overlapping intervals, which takes O(n) time. The space complexity is O(n) because we use a List to store the merged intervals, potentially storing all n intervals in the worst-case scenario where none overlap.

Efficient Approach

initializes two variables, min and max. Iterate through all intervals to find the minimum and maximum start points. Create a range array with a size equal to max - min + 1. This array is used to track the maximum endpoint for each start point within the range of min to max. For each interval, update the range array at the index corresponding to the interval's start point (adjusted by subtracting min). It ensures that each index stores the maximum endpoint seen for that start point. Initialize two pointers, start and end, to track the current interval being processed. Iterate through the range array, and for each non-zero value (indicating an interval's endpoint), check if the current index is within the current interval being processed (i <= end). If so, update the end to the maximum of the current end and the value at range[i]. If the current index is beyond the current end, it means the current interval has ended, and a new interval starts. The current interval is added to the result list, and start and end are updated to the new interval's start and end points. After the loop, add the last interval to the result list.

// TC: O(n)
// SC: O(n)

import java.util.LinkedList;

class MergeIntervals {
    public int[][] merge(int[][] intervals) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < intervals.length; i++) {
            min = Math.min(min, intervals[i][0]);
            max = Math.max(max, intervals[i][0]);
        }

        int[] range = new int[max - min + 1];
        for (int i = 0; i < intervals.length; i++) {
            range[intervals[i][0] - min] = Math.max(intervals[i][1] - min, range[intervals[i][0] - min]);
        }

        int start = 0, end = 0;
        LinkedList<int[]> result = new LinkedList<>();
        for (int i = 0; i < range.length; i++) {
            if (range[i] == 0) {
                continue;
            }
            if (i <= end) {
                end = Math.max(range[i], end);
            } else {
                result.add(new int[] { start + min, end + min });
                start = i;
                end = range[i];
            }
        }
        result.add(new int[] { start + min, end + min });

        return result.toArray(new int[result.size()][]);
    }

    public static void main(String args[]) {
        MergeIntervals mi = new MergeIntervals();
        int[][] intervals = { { 1, 3 }, { 2, 6 }, { 8, 10 }, { 15, 18 } };
        int[][] result = mi.merge(intervals);
        for (int[] interval : result) {
            System.out.println(interval[0] + " " + interval[1]);
        }
    }
}

Performance

The time complexity of the merge method is O(n). This is because we iterate through the intervals twice, once to calculate the minimum and maximum values and once to populate the range array. The space complexity is also O(n) because we use an additional array of size n to store the range values.

Thank you for reading!

Check out other DSA patterns here.

You can support me by buying me a book.