3.42 Merge and Sort Intervals (HackerRank)

3.42.1 Problem Metadata

3.42.2 Description

Note: This problem is nearly identical to Merge Intervals (LeetCode #56). The core algorithm and approach are the same.

Given an array of intervals [startTime, endTime], merge all overlapping intervals and return a sorted array of non-overlapping intervals.

Key Details: - Intervals may be provided in any order - Duplicates and fully contained intervals are allowed - Return intervals sorted by increasing start time

3.42.3 Examples

Example 1:

Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]
Explanation:
- Step 1: Sort intervals by start time (already sorted)
- Step 2: Initialize merged lc-list with first interval [1,3]
- Step 3: Compare [2,6] with last merged [1,3]. They overlap (2 ≤ 3), so merge into [1,6]
- Step 4: Compare [8,10] with last merged [1,6]. No overlap (8 > 6), append [8,10]
- Step 5: Compare [15,18] with last merged [8,10]. No overlap (15 > 10), append [15,18]
Result: [[1,6],[8,10],[15,18]]

Example 2:

Input: intervals = [[5, 10]]
Output: [[5, 10]]
Explanation: Only one interval, return as-is

Example 3:

Input: intervals = []
Output: []
Explanation: Empty input returns empty output

3.42.4 Input Format

  • First line: integer n denoting the number of intervals
  • Second line: integer 2 denoting the length of individual interval array
  • Next n lines: two space-separated integers startTime and endTime

Example:

4
2
1 3
2 6
8 10
15 18

3.42.5 Constraints

  • \(0 \le\) intervals.length \(\le 100000\)
  • intervals[i].length == 2 for all \(0 \le i <\) intervals.length
  • \(0 \le\) intervals[i][0] \(<\) intervals[i][1] \(\le 10^9\) for all \(0 \le i <\) intervals.length

3.42.6 Solution

3.42.6.1 Walkthrough

Sort intervals by start time, then sweep through the list and merge any interval that overlaps the current merged tail. When there is no overlap, append the current interval as a new block.

Cross-Reference: See Merge Intervals for the complete solution walkthrough, analysis, and implementation.

This problem uses the identical algorithm as LeetCode #56:

  1. Sort intervals by start time
  2. Merge overlapping intervals by comparing current.start with last.end
  3. Return the merged result sorted by start time

3.42.6.2 Key Differences from LeetCode #56

  • Input Format: HackerRank uses custom stdin format with separate lines for count and interval pairs
  • Output Format: Print each interval on a separate line as two space-separated integers
  • Edge Case Handling: Must handle empty input (n=0) explicitly

3.42.6.3 Analysis

  • Time Complexity: \(O(n \log n)\) - Dominated by sorting
  • Space Complexity: \(O(n)\) - For the output lc-list

3.42.6.4 Implementation Steps

Refer to Merge Intervals for detailed implementation steps.

3.42.6.5 Code - Java

Note: The actual HackerRank function signature uses List<List<Integer>> instead of int[][]. Both approaches use the same merge algorithm.

class Result {
    /*
     * Complete the 'mergeHighDefinitionIntervals' function below.
     *
     * The function is expected to return a 2D_INTEGER_ARRAY.
     * The function accepts 2D_INTEGER_ARRAY intervals as parameter.
     */

    public static List<List<Integer>> mergeHighDefinitionIntervals(
        List<List<Integer>> intervals) {

        if (intervals == null || intervals.isEmpty()) {
            return new ArrayList<>();
        }

        // Sort by start time: intervals[i].get(0)
        intervals.sort(Comparator.comparingInt(a -> a.get(0)));

        List<List<Integer>> merged = new ArrayList<>();

        // Add a copy of the first interval
        merged.add(new ArrayList<>(intervals.get(0)));

        for (int i = 1; i < intervals.size(); i++) {
            List<Integer> current = intervals.get(i);
            List<Integer> last = merged.get(merged.size() - 1);

            // If current.start <= last.end -> merge
            if (current.get(0) <= last.get(1)) {
                last.set(1, Math.max(last.get(1), current.get(1)));
            } else {
                // No overlap, add a new interval (copy to avoid aliasing)
                merged.add(new ArrayList<>(current));
            }
        }

        return merged;
    }
}