Java: Insert Interval

Thought Process

To solve the problem of inserting and merging intervals, we first determine the correct position to insert the new interval. This is done by iterating through the existing intervals and finding the first interval whose start is greater than or equal to the start of the new interval. Once the position is found, the new interval is inserted. After insertion, we merge overlapping intervals by comparing the end of the current interval with the start of the next interval. If they overlap, we merge them by updating the end of the current interval. This process continues until all intervals are processed, ensuring that the final list of intervals is non-overlapping. 

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
      
        List<int[]> list = new ArrayList<>(Arrays.asList(intervals));
      
        // Finding Position
        int position=list.size();
        for(int i=0;i<list.size();i++){
            int[] currentInterval = list.get(i);
            if(currentInterval[0] >= newInterval[0]){
                position = i;
                break;
            }
        }
        // Adding Element to the Position
        list.add(position,newInterval);
      
        // Merge the Intervals
        List<int[]> merged = new ArrayList<>();
      
        int[] refInterval = list.get(0);
        for(int i=1;i<list.size();i++){
      
            int[] currentInterval = list.get(i);
      
            int refStart = refInterval[0];
            int refEnd   = refInterval[1];
      
            int start = currentInterval[0];
            int end   = currentInterval[1];
      
            if(refEnd < start){
                merged.add(refInterval);
                refInterval = currentInterval;
            }
            else{
                refInterval[0] = refStart;
                refInterval[1] = Math.max(refEnd,end);
            }
        }
        merged.add(refInterval);
        return merged.toArray(new int[merged.size()][]);
    }
}

Code Complexity

Time Complexity: O(n)

The algorithm iterates through the array once to find the correct position to insert the new interval and then iterates through the array again to merge overlapping intervals. Each operation is O(1) on average.

Space Complexity: O(n)

The space required is proportional to the number of intervals, as we store the merged intervals in a new list.

Code copied!