Question

How to add a new interval into a sorted list of non‑overlapping intervals in Java

Answer 1

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

public class InsertInterval {

    public static List<int[]> insertInterval(List<int[]> intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;
        int n = intervals.size();

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

        // 2. Merge all intervals that DO overlap with the new interval.
        // Overlap condition: intervals[i].start <= newInterval.end
        while (i < n && intervals.get(i)[0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals.get(i)[0]);
            newInterval[1] = Math.max(newInterval[1], intervals.get(i)[1]);
            i++;
        }

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

        // 3. Add all remaining intervals (those starting AFTER new interval ends)
        while (i < n) {
            result.add(intervals.get(i));
            i++;
        }

        return result;
    }

    public static void main(String[] args) {
        List<int[]> intervals = new ArrayList<>();
        intervals.add(new int[]{1, 3});
        intervals.add(new int[]{6, 8});
        intervals.add(new int[]{13, 18});

        int[] newInterval1 = {9, 11};
        List<int[]> updated = insertInterval(intervals, newInterval1);

        int[] newInterval2 = {2, 5};
        updated = insertInterval(updated, newInterval2);

        System.out.println("Updated intervals:");
        for (int[] iv : updated) {
            System.out.print("[" + iv[0] + "," + iv[1] + "] ");
        }
    }
}



/*
run:

Updated intervals:
[1,5] [6,8] [9,11] [13,18]

*/

 

70+ SQL courses for beginners and professionals