package Leetcode.Intervals;

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

/**
 * Author: zhengstars
 * Date: 2024/06/16
 */
public class InsertInterval {
    public static int[][] insert(int[][] intervals, int[] newInterval) {
        // List to store the final result after merging intervals
        List<int[]> result = new ArrayList<>();

        // Length of the input intervals array
        int n = intervals.length;

        // Index for iterating through the intervals array
        int i = 0;

        // Add all intervals that end before the new interval starts
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);  // These intervals do not overlap with the new interval
            i++;
        }

        // Merge all intervals that overlap with the new interval
        while (i < n && intervals[i][0] <= newInterval[1]) {
            // Update the new interval to encompass the overlapping intervals
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }

        // Add the merged new interval to the result
        result.add(newInterval);

        // Add all remaining intervals that start after the new interval ends
        while (i < n) {
            result.add(intervals[i]);
            i++;
        }

        // Convert the result list to a two-dimensional array
        return result.toArray(new int[result.size()][]);
    }

    public static void main(String[] args) {
        // Test case 1
        int[][] intervals1 = { {1, 3}, {6, 9} };
        int[] newInterval1 = {2, 5};
        System.out.println("Result for intervals1: ");
        printResult(insert(intervals1, newInterval1)); // Expected output: [[1, 5], [6, 9]]

        // Test case 2
        int[][] intervals2 = { {1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16} };
        int[] newInterval2 = {4, 8};
        System.out.println("Result for intervals2: ");
        printResult(insert(intervals2, newInterval2)); // Expected output: [[1, 2], [3, 10], [12, 16]]
    }

    /**
     * Helper method to print a two-dimensional array of intervals.
     *
     * @param intervals The array of intervals to be printed.
     */
    private static void printResult(int[][] intervals) {
        for (int[] interval : intervals) {
            System.out.print("[" + interval[0] + ", " + interval[1] + "] ");
        }
        System.out.println();
    }
}