Make writing a habit together! This is the 13th day of my participation in the “Gold Digging Day New Plan · April More Text Challenge”. Click here for more details.

Topic describes

The array enjoyments is a set of intervals, where a single interval is enjoyments [I] = [Starti, endi]. You merge all overlapping ranges and return a non-overlapping array of ranges that exactly covers all of the ranges in the input.

Thought analysis

To judge whether the two intervals can be combined, in fact, it depends on whether ARr1 [1] and ARR0 [0] overlap (here we assume that ARR1 is relatively left-leaning). In order to let us know as much as possible whether the two intervals will have left-leaning, instead of enumerating all the results, we can first sort the whole.

When sorting, we can increment the sort based on the left endpoint, if the current array and the last array overlap interval, we think we can merge, otherwise add to the result array.

For example, add the array to the result array and compare it with the right end of the last element.

The left pointer points to the beginning of the current interval, and the right pointer starts to look forward. If the starting value of the subsequent interval is smaller than the right endpoint of Max, it indicates that the interval is repeated and can be merged together.

Otherwise, the left and right ends of the left pointer are stored in the result array.

Code implementation

vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.size() = =0) {
            return {};
        }
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> merged;
        for (int i = 0; i < intervals.size(a); ++i) {int L = intervals[i][0], R = intervals[i][1];
            if(! merged.size() || merged.back(to)1] < L) {
                merged.push_back({L, R});
            }
            else {
                merged.back(to)1] = max(merged.back(to)1], R); }}return merged;
    }

Copy the code

conclusion

I wanted to optimize it in a greedy way, such as sorting the right endpoints from large to small, and traversing to delete the small right endpoints, but it didn’t make sense.