Merge Overlapping Intervals

/*
 * Problem : Merge intervals.
 * Input   : n, then n lines with start and end.
 * Output  : The merged intervals.
 * Approach: Sort by start.
 * Time    : O(n log n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(String[] lines) {
        int n = Integer.parseInt(lines[0]);
        int[][] intervals = new int[n][2];
        for (int i = 0; i < n; i++) {
            String[] parts = lines[i + 1].split(" ");
            intervals[i][0] = Integer.parseInt(parts[0]);
            intervals[i][1] = Integer.parseInt(parts[1]);
        }

        // Step 1: Sort the intervals by their start. Then overlapping intervals stand next to each other.
        java.util.Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));

        java.util.List<int[]> merged = new java.util.ArrayList<>();
        for (int[] interval : intervals) {
            int[] last = merged.isEmpty() ? null : merged.get(merged.size() - 1);

            // Step 2: If the interval starts before the last merged one ends, they overlap. Extend the end.
            if (last != null && interval[0] <= last[1]) {
                last[1] = Math.max(last[1], interval[1]);
            } else {
                // Step 3: Otherwise start a new merged interval.
                merged.add(new int[] {interval[0], interval[1]});
            }
        }

        String[] output = new String[merged.size()];
        for (int i = 0; i < output.length; i++) {
            output[i] = merged.get(i)[0] + " " + merged.get(i)[1];
        }
        return output;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        java.util.List<String> all = new java.util.ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (!line.isEmpty()) {
                all.add(line);
            }
        }
        String[] lines = all.toArray(new String[0]);
        System.out.println(String.join("\n", solve(lines)));
    }
}