一、相差不超过k的最多数

给定一个数组，选择一些数，要求选择的数中任意两数差的绝对值不超过 k 。问最多能选择多少个数？
输入描述：
第一行输入两个正整数 n和k。
第二行输入 n个正整数ai，用空格隔开，表示这个数组。
输出描述：
一个正整数，代表能选的最多数量。
数据范围：
1≤n≤2×10^5

1≤k,ai≤10^9

示例1
输入：
5 3
2 1 5 3 2
复制
输出：
4
复制
说明：
显然，1和5不能同时选。所以最多只能选4个数。

解法:

由题知，可以先排序，寻找最大值与最小值的差在差值范围内的最大值与最小值，计算允许差值区间的数据个数，更新最大与最小值，计算个数，取个数最大值为结果

#include
#include
#include
using namespace std;
int main()
{
    int n,gap,ret;
    cin>>n>>gap;
    vector<int>v;
    for(int i=0;i<n;i++)
    {
        cin>>ret;
        v.push_back(ret);
    }
    sort(v.begin(),v.end());
    int l=0,res=0;
    for(int i=0;i<n;i++)
    {
        while(v[i]-v[l]>gap)
            l++;
        res=max(res,i-l+1);
    }
    cout<<res;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

二、合并区间

解法: 排序+贪心(推荐)

• 既然要求重叠后的区间按照起点位置升序排列，我们就将所有区间按照起点位置先进行排序。使用sort函数进行排序，重载比较方式为比较interval结构的start变量。
• 排序后的第一个区间一定是起点值最小的区间，我们将其计入返回数组res，然后遍历后续区间。
• 后续遍历过程中，如果遇到起点值小于res中最后一个区间的末尾值的情况，那一定是重叠，取二者最大末尾值更新res中最后一个区间即可。
• 如果遇到起点值大于res中最后一个区间的末尾值的情况，那一定没有重叠，后续也不会有这个末尾的重叠区间了，因为后面的起点只会更大，因此可以将它加入res。
  

class Solution {
public:
    //重载比较
    static bool cmp(Interval &a, Interval &b) { 
        return a.start < b.start;
    }
    
    vector<Interval> merge(vector<Interval> &intervals) {
        vector<Interval> res;
        //去除特殊情况
        if(intervals.size() == 0) 
            return res;
        //按照区间首排序
        sort(intervals.begin(), intervals.end(), cmp); 
        //放入第一个区间
        res.push_back(intervals[0]); 
        //遍历后续区间，查看是否与末尾有重叠
        for(int i = 1; i < intervals.size(); i++){ 
            //区间有重叠，更新结尾
            if(intervals[i].start <= res.back().end) 
                res.back().end = max(res.back().end, intervals[i].end);
            //区间没有重叠，直接加入
            else 
                res.push_back(intervals[i]);
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

时间复杂度：O(n$\log 2$n)，排序的复杂度为O(n$\log 2$n)，后续遍历所有区间的复杂度为O(n)，属于低次幂，忽略
空间复杂度：O(1)，res为返回必要空间，没有使用额外辅助空间