剑指offer专项突击版第25天

剑指 Offer II 074. 合并区间

排序+贪心

1. 将区间按左端点升序排序，那么就有一个性质：下个区间的左端点<=当前右端点<=当前左端点。
2. 容易想到如果当前右端点小于下个区间的左端点时就不可能合并了，如果是大于等于的话在当前右端点和下个右端点取一个最大即可。

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$ 内数据的范围 $[0,1000]$ 完全可以直接计数排序， $O(N)$ 的时间复杂度。
注意：在完成把前面部分插入后，while条件里面会出现-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;
    }
};