2406. 将区间分为最少组数-差分数组

2406. 将区间分为最少组数-差分数组

给你一个二维整数数组 intervals ，其中 intervals[i] = [lefti, righti] 表示 闭 区间 [lefti, righti] 。

你需要将 intervals 划分为一个或者多个区间 组 ，每个区间 只 属于一个组，且同一个组中任意两个区间 不相交 。

请你返回 最少 需要划分成多少个组。

如果两个区间覆盖的范围有重叠（即至少有一个公共数字），那么我们称这两个区间是 相交 的。比方说区间 [1, 5] 和 [5, 8] 相交。

示例 1：

输入：intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]]
输出：3
解释：我们可以将区间划分为如下的区间组：

• 第 1 组：[1, 5] ，[6, 8] 。
• 第 2 组：[2, 3] ，[5, 10] 。
• 第 3 组：[1, 10] 。
  可以证明无法将区间划分为少于 3 个组。

示例 2：

输入：intervals = [[1,3],[5,6],[8,10],[11,13]]
输出：1
解释：所有区间互不相交，所以我们可以把它们全部放在一个组内。

这题用差分数组去做啊
解题代码如下：

#define size 1000005




int minGroups(int** intervals, int intervalsSize, int* intervalsColSize){

int a[size];
for(int i=0;i<size;i++){
    a[i]=0;
}
for(int i=0;i<intervalsSize;i++){
    a[intervals[i][0]]=a[intervals[i][0]]+1;
    a[intervals[i][1]+1]=a[intervals[i][1]+1]-1;


}
int re=0;
int m=a[0];
for(int i=1;i<size;i++){
    m=m+a[i];
    re=fmax(re,m);



}
return re;
  

}
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
30
31