C++: Merge Interval

Thought Process

To merge overlapping intervals, we first sort the intervals based on their start times. This allows us to easily identify and merge overlapping intervals in a single pass. We initialize a reference interval with the first interval and iterate through the sorted intervals. If the current interval does not overlap with the reference interval, we add the reference interval to the result and update the reference interval to the current one. If they overlap, we merge them by updating the end time of the reference interval to the maximum of the two end times. Finally, we add the last reference interval to the result. 

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {

        // Sort the vector
        sort(intervals.begin(),intervals.end());

        vector<vector<int>> ans;
        
        // Take reference interval
        vector<int> ref = intervals[0];
        for(int i=1;i<intervals.size();i++){

            vector<int> currentInterval = intervals[i];

            int refStart = ref[0];
            int refEnd   = ref[1];

            int start = currentInterval[0];
            int end   = currentInterval[1];

            if(refEnd < start){
                // No overlapping
                ans.push_back(ref);
                ref.swap(currentInterval);
            }
            else{
                ref[0] = refStart;
                ref[1] = max(refEnd,end);
            }
        }
        ans.push_back(ref);
        return ans;
    }
};

Code Complexity

Time Complexity: O(n log n)

The algorithm sorts the intervals, which takes O(n log n) time, and then iterates through the sorted intervals once, which takes O(n) time. Therefore, the overall time complexity is O(n log n).

Space Complexity: O(n)

The algorithm uses additional space to store the result, which in the worst case can be O(n) if no intervals are merged.

Code copied!