Insert Interval

class Solution {
public:
    vector<vector<int>> mergeIntervals(vector<vector<int>>& existingIntervals, vector<int>& newRange) {
        if (existingIntervals.empty()) {
            return {newRange};
        }

        int count = existingIntervals.size();
        int keyValue = newRange[0];
        int low = 0, high = count - 1;

        while (low <= high) {
            int middle = (low + high) / 2;
            if (existingIntervals[middle][0] < keyValue) {
                low = middle + 1;
            } else {
                high = middle - 1;
            }
        }

        existingIntervals.insert(existingIntervals.begin() + low, newRange);
        
        vector<vector<int>> result;
        for (const auto& range : existingIntervals) {
            if (result.empty() || result.back()[1] < range[0]) {
                result.push_back(range);
            } else {
                result.back()[1] = max(result.back()[1], range[1]);
            }
        }

        return result;
    }
};

Solve the "Insert Interval" problem in C++ by designing a function that merges a new interval into a list of existing sorted intervals, efficiently handling overlapping intervals. To implement the solution, follow these steps:

1. Check if the existing intervals collection is empty. If so, return a list containing only the new interval.
2. Determine the position in the existing intervals where the new interval should be inserted by implementing a binary search. This efficient search reduces the complexity by comparing the start of the new interval to the starts of existing intervals.
3. Insert the new interval into the correct position in the sorted list.
4. Iterate through the sorted list and merge any intervals that overlap. Utilize conditions to check if the intervals overlap and merge them by updating the end value of the last interval in the result list.
5. Return the updated list of intervals as the result.

This approach ensures that the list remains in order after the insertion of the new interval and efficiently merges overlapping intervals in a single traversal. This solution capitalizes on binary search for insertion, making it well-suited for large lists of intervals.

class Solution {
    public int[][] insertInterval(int[][] existingIntervals, int[] intervalToAdd) {
        if (existingIntervals.length == 0) {
            return new int[][] { intervalToAdd };
        }

        int totalIntervals = existingIntervals.length;
        int insertPoint = intervalToAdd[0];
        int low = 0, high = totalIntervals - 1;

        while (low <= high) {
            int mid = (low + high) / 2;
            if (existingIntervals[mid][0] < insertPoint) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        List<int[]> combinedIntervals = new ArrayList<>();
        for (int i = 0; i < low; i++) {
            combinedIntervals.add(existingIntervals[i]);
        }
        combinedIntervals.add(intervalToAdd);
        for (int i = low; i < totalIntervals; i++) {
            combinedIntervals.add(existingIntervals[i]);
        }

        List<int[]> finalIntervals = new ArrayList<>();
        for (int[] interval : combinedIntervals) {
            if (
                finalIntervals.isEmpty() ||
                finalIntervals.get(finalIntervals.size() - 1)[1] < interval[0]
            ) {
                finalIntervals.add(interval);
            } else {
                finalIntervals.get(finalIntervals.size() - 1)[1] = Math.max(
                    finalIntervals.get(finalIntervals.size() - 1)[1],
                    interval[1]
                );
            }
        }

        return finalIntervals.toArray(new int[0][]);
    }
}

This solution handles the insertion of a new interval into a list of existing non-overlapping intervals in Java. The method insertInterval accepts two parameters: existingIntervals, a 2D array of intervals, and intervalToAdd, a single interval array.

Start by checking if the existingIntervals is empty. If true, simply return an array containing only the intervalToAdd.

Calculate totalIntervals from the length of existingIntervals and determine insertPoint from the first value of intervalToAdd. Use binary search to find the appropriate location to insert the new interval without disrupting the order. The while loop efficiently narrows down the insertion point.

Once the position is determined:

• Iterate over the intervals up to the determined point, adding them to combinedIntervals.
• Add the intervalToAdd to combinedIntervals.
• Include the remaining intervals from existingIntervals into combinedIntervals.

Now, merge any overlapping intervals:

• Iterate through combinedIntervals.
• If finalIntervals is empty or the last interval in finalIntervals does not overlap with the current interval, simply add the current interval.
• If there is an overlap (determined by the end of the last interval in finalIntervals being greater than or equal to the start of the current interval), merge the intervals by updating the end point.

Finally, convert the List<int[]> to a 2D array and return this array. This method ensures that the new list of intervals remains sorted and non-overlapping.

// Structure for linked list node
typedef struct LinkNode {
    int range[2];
    struct LinkNode* next;
} LinkNode;

int** integrateIntervals(int** intervals, int sizeIntervals, int* colSizes,
                         int* newRange, int sizeNewRange, int* sizeResult,
                         int** colSizeResult) {
    // Directly return newRange if intervals is empty
    if (sizeIntervals == 0) {
        *sizeResult = 1, *colSizeResult = malloc(sizeof(int));
        **colSizeResult = 2;
        int** outcome = malloc(sizeof(int*));
        *outcome = malloc(2 * sizeof(int));
        memcpy(*outcome, newRange, 2 * sizeof(int));
        return outcome;
    }

    int count = sizeIntervals;
    int startPoint = newRange[0];
    int begin = 0, end = count - 1;

    // Binary search for the correct insertion position for newRange
    while (begin <= end) {
        int middle = (begin + end) / 2;
        if (intervals[middle][0] < startPoint) {
            begin = middle + 1;
        } else {
            end = middle - 1;
        }
    }

    // Insert newRange using the located position
    LinkNode* root = NULL;
    LinkNode** current = &root;
    for (int i = 0; i < begin; ++i) {
        *current = malloc(sizeof(LinkNode));
        (*current)->next = NULL;
        memcpy((*current)->range, intervals[i], sizeof(int) * 2);
        current = &((*current)->next);
    }
    *current = malloc(sizeof(LinkNode));
    (*current)->next = NULL;
    memcpy((*current)->range, newRange, sizeof(int) * 2);
    current = &((*current)->next);
    for (int i = begin; i < count; ++i) {
        *current = malloc(sizeof(LinkNode));
        (*current)->next = NULL;
        memcpy((*current)->range, intervals[i], sizeof(int) * 2);
        current = &((*current)->next);
    }

    // Combine overlapping intervals
    int** finalIntervals = malloc(1001 * sizeof(int*));
    int* sizesFinal = malloc(1001 * sizeof(int));
    int countFinal = 0;
    for (LinkNode* ptr = root; ptr != NULL; ptr = ptr->next) {
        int* range = ptr->range;
        // Append new interval or merge it if it overlaps
        if (countFinal == 0 || finalIntervals[countFinal - 1][1] < range[0]) {
            finalIntervals[countFinal] = malloc(2 * sizeof(int));
            memcpy(finalIntervals[countFinal], range, 2 * sizeof(int));
            sizesFinal[countFinal] = 2;
            ++countFinal;
        } else {
            finalIntervals[countFinal - 1][1] =
                (finalIntervals[countFinal - 1][1] < range[1])
                    ? range[1]
                    : finalIntervals[countFinal - 1][1];
        }
    }
    *sizeResult = countFinal, *colSizeResult = sizesFinal;

    return finalIntervals;
}

The provided C code defines a function integrateIntervals used to insert a new interval into a sorted list of non-overlapping intervals and merge where necessary. Here's an explanation of how the code achieves this:

• You initiate by checking if the existing intervals list is empty. If empty, allocate and return the new interval as the only range.

• To locate where the new interval should be inserted within the existing intervals, a binary search is implemented. This ensures efficient insertion, particularly beneficial for large lists.

• After determining the insertion point, the existing intervals and the new range are re-organized into a linked list using LinkNode structures, adding intervals in sorted order up to the insertion point, then the new interval, followed by the remaining intervals.

• With all ranges inserted into the linked list, the next step combines any overlapping intervals. It iterates through the linked list, comparing each interval with the previous one to either merge overlapping intervals or to continue adding distinct intervals.

• Dynamic memory is utilized throughout the process, especially when dealing with the results and the dynamically-sized list of merged intervals, ensuring the flexibility to handle a varying number of intervals.

• Finally, it returns the dynamically-allocated list of merged intervals along with their sizes, suitably updating the parameters to reflect the correct output size for further processing.

The algorithm systematically constructs the solution by restructuring data, applying a mix of binary search, linked lists, and dynamic allocation, ensuring efficiency and scalability in dealing with interval merging tasks in C.

var mergeIntervals = function (existingRanges, newRange) {
    if (existingRanges.length === 0) {
        return [newRange];
    }

    let total = existingRanges.length;
    let start = newRange[0];
    let begin = 0,
        end = total - 1;

    while (begin <= end) {
        let middle = Math.floor((begin + end) / 2);
        if (existingRanges[middle][0] < start) {
            begin = middle + 1;
        } else {
            end = middle - 1;
        }
    }

    existingRanges.splice(begin, 0, newRange);

    let combined = [];
    for (let range of existingRanges) {
        if (combined.length === 0 || combined[combined.length - 1][1] < range[0]) {
            combined.push(range);
        } else {
            combined[combined.length - 1][1] = Math.max(
                combined[combined.length - 1][1],
                range[1],
            );
        }
    }

    return combined;
};

The provided JavaScript code defines a function mergeIntervals which is designed to insert a new interval (newRange) into an existing list of sorted intervals (existingRanges) and then merge all overlapping intervals. The function handles the entire process efficiently by utilizing a binary search to find the correct insertion point for the new interval, which helps maintain the sorted order. Once the new interval is inserted, the function then iterates over the list to merge any intervals that overlap.

Here’s a breakdown of the process:

• Check for Empty List: If existingRanges is empty, the function immediately returns a list containing only the newRange.

• Binary Search for Insertion Point: The function uses binary search to determine the correct insertion point for the newRange. This ensures that the intervals remain sorted after insertion, optimizing the merging phase.

• Insert the New Interval: Using the found insertion point, the newRange is inserted into existingRanges.

• Merge Overlapping Intervals: Starting with an empty list combined, the function iterates through existingRanges. For each interval:

  • If combined is empty or the last interval in combined does not overlap with the current interval, the current interval is added to combined.
  • If there is an overlap, the last interval in combined is extended to encompass the current interval.

• Output: The function returns the merged intervals as the final result.

This approach ensures that the function operates efficiently, with a time complexity driven by the binary search and a single pass merge operation. The binary search operates in O(log n) time, and merging the intervals takes O(n) time, leading to an overall efficient O(n log n) complexity for scenarios involving large data sets.

class Solution:
    def mergeInsert(self, spans: List[List[int]], newSpan: List[int]) -> List[List[int]]:
        if not spans:
            return [newSpan]

        length = len(spans)
        start = newSpan[0]
        low, high = 0, length - 1

        while low <= high:
            mid = (low + high) // 2
            if spans[mid][0] < start:
                low = mid + 1
            else:
                high = mid - 1

        spans.insert(low, newSpan)

        merged = []
        for span in spans:
            if not merged or merged[-1][1] < span[0]:
                merged.append(span)
            else:
                merged[-1][1] = max(merged[-1][1], span[1])

        return merged

This program outlines a solution for inserting a new interval into a list of non-overlapping intervals and then merging any overlapping intervals in Python. Here's how it accomplishes this task:

• Evaluate if the list of intervals is empty. If yes, the new interval is simply returned as the result.

• Initiate a binary search to find the correct position to insert the new interval based on its start point. This ensures that the list remains sorted after insertion, which is crucial for the merging step.

• Insert the new interval into the determined position in the list.

• Traverse through the list of intervals. For each interval:

  • If there's no overlap with the last interval in the result list (merged), simply add the interval to merged.
  • If an overlap is detected, merge the current interval with the last one in merged by updating the end of the last interval in merged to be the maximum of both ends.

The end result is a list of merged intervals, reflecting the inclusion of the new interval in the correct sequence without overlap. This approach ensures that the operation is efficient, mostly due to the binary search step which operates in logarithmic time complexity, making this method suitable for handling large sets of intervals effectively.