56. Merge Intervals

Leetcode

📝 Problem Details

• Title: 56. Merge Intervals
• Link: https://leetcode.com/problems/merge-intervals/
• Difficulty: Medium
• Tags/Categories: Arrays Sorting

💭What Were My Initial Thoughts?

- a simplistic view of the problem is just comparing the last value of the previous element with the first value of the current element
- how can we do this efficiently with our array
- the input array isnt sorted when passed into our function

🤔What Did I Struggle With?

i read the question / example cases incorrectly and thought were were combinind all elements, not just appending the range

💡 Explanation of Solution

1. Sort the input array
2. create a results vector and push the first element of out input array into it
3. iterate through the input array and check the last element in our results vector
4. compare the second value in our last element to the first value in our current element in the intervals array
5. make the second value in our last element the max between the two
6. return the results vector

⌛ Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)
- an additional results vector of size n

💻 Implementation of Solution

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> result;
        result.push_back(intervals[0]);
        
        for(int i=1; i < intervals.size(); i++) {
            vector<int>& last = result.back();
            
            if(last[1] >= intervals[i][0]) last[1] = max(last[1], intervals[i][1]);
            else result.push_back(intervals[i]);
        }
        return result;
    }
};