The 25th day of the special assault version of the sword offer

剑指 Offer II 074. 合并区间

排序+贪心

1. Sort the interval by the left endpoint in ascending order,Then there is a property：The left endpoint of the next interval<=当前右端点<=当前左端点.
2. It is easy to think that it is impossible to merge if the current right endpoint is smaller than the left endpoint of the next interval,If it is greater than or equal to, then take the maximum of the current right endpoint and the next right endpoint.

class Solution {
    
public:
    bool cmp(vector<int> &a, vector<int> &b) {
    
        if(a[0] != b[0]) return a[0] < b[0];
        return a[1] < b[1];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
    
        sort(intervals.begin(), intervals.end());
        int st = intervals[0][0], ed = intervals[0][1];
        vector<vector<int>> res;
        for(int i = 1; i < intervals.size(); i++) {
    
            const auto seg = intervals[i];
            if(ed < seg[0]) {
    
                res.emplace_back(vector<int>{
    st,ed});
                st = seg[0];
                ed = seg[1];
            } else {
    
                ed = max(ed,seg[1]);
            }
        }
        if(res.empty() || ed != res.back()[1]) res.emplace_back(vector<int>{
    st,ed});  
        return res;
    }
};

剑指 Offer II 075. 数组相对排序

计数排序

发现 $arr1$ range of data $[0,1000]$ It can be directly counted and sorted, $O(N)$ 的时间复杂度.
注意：After you finish inserting the front part,whileconditions will appear-1,需要加上>0条件.

class Solution {
    
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
    
        int cnts[1010] = {
    0};
        vector<int> res;
        for(auto num: arr1) cnts[num]++;

        for(auto num: arr2) 
            while(cnts[num]--) res.emplace_back(num);

        for(int i = 0; i <= 1000; i++)
            while(cnts[i]-- > 0) 
				res.emplace_back(i);

        return res;
    }
};