algoadvance

Leetcode 56. Merge Intervals

Problem Statement

You are given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Clarifying Questions

  1. Input Format:
    • What should be done if the input array is empty?
    • Are the intervals sorted by their start time initially?
  2. Output Format:
    • Should the output be sorted by start times of the intervals?
    • Are there any constraints on the size of the input array?
  3. Edge Cases:
    • How should single intervals be handled?
    • Is the input guaranteed to have valid intervals where start is less than or equal to end?

Code

import java.util.*;

public class MergeIntervals {

    public static int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) {
            return intervals;  // If there is 0 or 1 interval, return it as is.
        }

        // Sort intervals based on the start time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        List<int[]> merged = new ArrayList<>();
        int[] currentInterval = intervals[0];
        merged.add(currentInterval);

        for (int[] interval : intervals) {
            int currentEnd = currentInterval[1];
            int nextStart = interval[0];
            int nextEnd = interval[1];

            // Check for overlap
            if (currentEnd >= nextStart) {
                // Merge intervals
                currentInterval[1] = Math.max(currentEnd, nextEnd);
            } else {
                // No overlap, add the interval to the list
                currentInterval = interval;
                merged.add(currentInterval);
            }
        }

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

    public static void main(String[] args) {
        int[][] intervals = // use example from above
        System.out.println(Arrays.deepToString(merge(intervals))); // [[1, 6], [8, 10], [15, 18]]

        intervals = new int[][]// use example from above
        System.out.println(Arrays.deepToString(merge(intervals))); // [[1, 5]]
    }
}

Strategy

  1. Initial Handling:
    • If there are zero or one intervals, return them as they are already “merged.”
  2. Sorting:
    • Sort intervals based on their start time to facilitate the merging process.
  3. Merging Process:
    • Iterate through the sorted intervals, and for each interval, compare it with the last added interval in the merged list.
    • If there is an overlap (i.e., the end of the current internal is greater than or equal to the start of the next interval), update the end of the merged interval to the maximum end of both intervals.
    • If there is no overlap, add the new interval as a new entry to the merged list.
  4. Conversion:
    • Convert the list of merged intervals back to an array before returning.

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI