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)

Discussion (0)