DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

Cover image for Leetcode Merge Intervals - Solution & Video Explaination
shubhsheth
shubhsheth

Posted on

Leetcode Merge Intervals - Solution & Video Explaination

Solution

vector<vector<int>> merge(vector<vector<int>>& intervals) {

    // Edge Cases
    if (intervals.size() <= 1) {
        return intervals;
    }

    // Sorting
    sort(intervals.begin(), intervals.end());

    // Merging
    vector<vector<int>> result;
    result.push_back(intervals[0]);
    for (int i = 1; i < intervals.size(); ++i) {
        if (intervals[i][0] <= result.back()[1]) {
            if (intervals[i][1] > result.back()[1]) {
                result.back()[1] = intervals[i][1];
            }
        } else {
            result.push_back(intervals[i]);
        }
    }
    return result;
}
Enter fullscreen mode Exit fullscreen mode
def merge(intervals):

    if len(intervals) <= 1:
        return intervals

    intervals.sort()

    merged = [intervals[0]]

    for interval in intervals[1:]:
        if interval[0] <= merged[-1][1]:
            if interval[1] > merged[-1][1]:
                merged[-1][1] = interval[1]
        else:
            merged.append(interval)

    return merged
Enter fullscreen mode Exit fullscreen mode

Complexity

Runtime: O(nlogn)
Space: O(n)

Top comments (0)

DEV

Thank you.

Β 
Thanks for visiting DEV, we’ve worked really hard to cultivate this great community and would love to have you join us. If you’d like to create an account, you can sign up here.