56. Merge Intervals - cocoder39/coco39_LC GitHub Wiki

56. Merge Intervals

a follow up: merged 2 sorted interval list (986) and merge k sorted interval list (986 + divide-and-conquer merge k sorted list)

===================================== Notes 2020:

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        merged = []
        for start, end in intervals:
            if not merged or merged[-1][1] < start:
                merged.append([start, end])
            else:
                merged[-1][1] = max(merged[-1][1], end)
        return merged

Alternative option is to first build connections between each pair of intervals then we can find intervals indirectly being connected. From there we can perform dfs or unionFind to merge all connected intervals. T = O(n^2)

=================================================================

tip: use return i1.start <= i2.start in comparator would cause runtime error.

strict order: a correct comparator should have determined behavior:

  • transitive. if return true for a < b and b < c, then return true for a < c
  • no conflict. if return true for a < b, then false for b < a
  • if return false for both a < b and b < a, a == b

in my case, I cannot use ! (a <= b) && ! (b <= a) to determine a == b. Hence, always use strict ordering

vector<Interval> merge(vector<Interval>& intervals) {
        sort(intervals.begin(), intervals.end(), [](Interval i1, Interval i2){
            //time limit exceeded: return i1.start <= i2.start;
            return i1.start < i2.start;
        });
        
        vector<Interval> res;
        for (int i = 0; i < intervals.size(); i++) {
            if (res.empty() || intervals[i].start > res.back().end) {
                res.push_back(intervals[i]);
            }
            else { //overlap
                res.back().end = max(res.back().end, intervals[i].end);
            }
        }
        return res;
    }
⚠️ **GitHub.com Fallback** ⚠️