LeetCode Solution 57 - Insert Interval

Problem Statement

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi], sorted in ascending order by starti, and an interval newInterval = [start, end] that you need to insert into intervals.

The intervals should still be non-overlapping and sorted in ascending order after insertion.

Example 1:

Input:

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

Output:

[[1,5],[6,9]]

Example 2:

Input:

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

Output:

[[1,2],[3,10],[12,16]]

---

Optimal Approach

To efficiently insert the new interval while maintaining the sorted and non-overlapping properties, we can use a greedy algorithm. We traverse the intervals once and handle the three cases:

1. Non-overlapping before the new interval: Add intervals that end before newInterval starts.
2. Overlapping intervals: Merge all intervals that overlap with newInterval.
3. Non-overlapping after the new interval: Add intervals that start after newInterval ends.

This approach ensures that we maintain order while minimizing unnecessary operations.

---

C++ Solution (LeetCode-Submittable)

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> result;
        int i = 0, n = intervals.size();
        
        // Step 1: Add all intervals that end before newInterval starts
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.push_back(intervals[i]);
            i++;
        }
        
        // Step 2: Merge overlapping intervals
        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);
        
        // Step 3: Add remaining intervals
        while (i < n) {
            result.push_back(intervals[i]);
            i++;
        }
        
        return result;
    }
};

---

Step-by-Step Explanation

1. Step 1 (Before Merging):
   • Traverse the intervals list and append all intervals that end before newInterval starts.
   • This ensures non-overlapping intervals are added to the result as is.
2. Step 2 (Merging Overlapping Intervals):
   • If an interval overlaps, merge it by adjusting newInterval's start and end boundaries.
   • Keep merging until we find an interval that doesn’t overlap.
3. Step 3 (After Merging):
   • Append newInterval after merging.
   • Add any remaining intervals after newInterval.

---

Dry Run / Execution Steps

Given Input:

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

Execution:

1. Add [1,2] to result.
2. Merge [3,5] with [4,8] → [3,8]
3. Merge [6,7] → [3,8]
4. Merge [8,10] → [3,10]
5. Add remaining [12,16] to result.

Final Output:

[[1,2],[3,10],[12,16]]

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Drawbacks
Brute Force (Insert & Sort)	O(N log N)	O(N)	Sorting adds extra overhead
Two-Pointer Merge	O(N)	O(N)	Optimal solution

Why is the Two-Pointer Merge the Best Approach?

• Linear Time Complexity: The traversal is O(N), making it highly efficient.
• No Extra Sorting Needed: Unlike brute-force, we merge as we traverse, ensuring O(N) time.
• Minimal Space Usage: We only store the result O(N), no extra auxiliary space required.

---

Complexity Analysis

• Time Complexity: O(N), where N is the number of intervals.
• Space Complexity: O(N), as we store the merged result in a new list.

---

Conclusion

The two-pointer merge method provides an optimal, efficient, and clean solution to the "Insert Interval" problem. It ensures minimal operations while maintaining sorted and non-overlapping intervals.

Happy Coding! 🚀