algoadvance

Leetcode 57. Insert Interval

Problem Statement

Given a set of non-overlapping intervals intervals where intervals[i] = [start_i, end_i], insert a new interval newInterval = [start, end] into intervals such that intervals is still sorted in ascending order by start and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return the intervals after the insertion.

Example:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]

Clarifying Questions

  1. Are the intervals in intervals guaranteed to be sorted by their start values initially?
    • Yes, the intervals are initially sorted.
  2. Can the newInterval overlap with multiple intervals in intervals?
    • Yes, it can overlap with multiple intervals.
  3. What should be done if newInterval does not overlap with any of the intervals?
    • The newInterval should simply be inserted in its correct position to maintain the sorted order.

Strategy

Approach:

  1. Initialization:
    • Create a result vector to store the final merged intervals.
    • Use two pointers to handle the intervals before and after the merge.
  2. Iteration:
    • Iterate through the given intervals and:
      • Add all intervals that end before the newInterval starts directly to the result.
      • Merge all intervals that overlap with newInterval, updating the newInterval to the merged interval’s boundaries.
      • Add the rest of the intervals after the newInterval ends to the result.
  3. Insertion:
    • If newInterval has not been added yet, add it to the result.
  4. Return the result:
    • Return the updated list of intervals.

Time Complexity:

Code

#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    vector<vector<int>> result;
    int i = 0;
    int n = intervals.size();

    // Add all intervals that end before newInterval starts
    while (i < n && intervals[i][1] < newInterval[0]) {
        result.push_back(intervals[i]);
        i++;
    }

    // Merge all overlapping intervals with newInterval
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = min(newInterval[0], intervals[i][0]);
        newInterval[1] = max(newInterval[1], intervals[i][1]);
        i++;
    }
    result.push_back(newInterval);

    // Add all remaining intervals after newInterval
    while (i < n) {
        result.push_back(intervals[i]);
        i++;
    }

    return result;
}

This solution handles the insertion of the new interval by maintaining the sorted order and merging overlapping intervals into a single, unified interval. The result is a list of non-overlapping intervals sorted by their start times.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI