线段覆盖长度
一、总结
一句话总结：a、贪心的话级排序；b、线段树
1、如果线段的起点Ai和终点Bi的绝对值可能达到109，如果用贪心怎么做？
不要用桶去计算区间覆盖的长度，正确的做法是排序后比较区间就好
二、线段覆盖长度
给定一些线段，线段有起点和终点，求这些线段的覆盖长度，重复的部分只计算一次。
方法一：
首先说排序对于处理很多问题都是非常有效的，例如寻找兄弟单词等问题中，经过排序处理后，问题就明朗了很多；
线段覆盖长度也是这样，将线段排序后，然后扫描一遍就可以得到覆盖的长度。具体做法：排序时，先按线段的起始端点排序，如果始点相同则按照末端点排，然后从头扫描，寻找连续段；所谓连续段即下一条线段的始点不大于当前线段的末点就一直扫描，直到找到断层的，计算当前长度，然后继续重复扫描直到最后，便得总长度。代码如下：
#include<iostream>
using namespace std;
/* 排序求线段覆盖长度 */
#define MAXN 100 // 设线段数不超过100
struct segment
{
int start;
int end;
}segArr[100];
/* 计算线段覆盖长度 */
int lenCount(segment * segArr, int size)
{
int length = 0, start = 0, end = 0;
for(int i = 0; i < size; ++i)
{
start = segArr[i].start;
end = segArr[i].end;
while(end >= segArr[i+1].start)
{
++i;
end = segArr[i].end > end ? segArr[i].end : end;
}
length += (end - start);
}
return length;
}
/* 快排比较函数 */
int cmp(const void * p, const void *q)
{
if(((segment *)p)->start != ((segment *)q)->start)
{
return ((segment *)p)->start - ((segment *)q)->start;
}
return ((segment *)p)->end - ((segment *)q)->end;
}
/* 测试线段 answer: 71 */
int segTest[10][2] = {
5, 8, 10, 45, 0, 7,
2, 3, 3, 9, 13, 26,
15, 38, 50, 67, 39, 42,
70, 80
};
void main()
{
for(int i = 0; i < 10; ++i) // 测试线段
{
segArr[i].start = segTest[i][0];
segArr[i].end = segTest[i][1];
}
qsort(segArr,10,sizeof(segment),cmp); // 排序
printf("length: %d
",lenCount(segArr,10)); // 计算
}
方法二：
当我学习线段树这个数据结构时，百度谷歌一番，发现关于它的资料真是铺天盖地，而线段树的经典应用就是求线段覆盖长度了，线段树本身的数据结构很简单，关键在于怎么用，线段结构如何设计，查询、更新等操作如何具体问题具体处理，这里就不列举了，改天多做几道题练练手。对于本题，在插入线段的时候，标记覆盖，之后统计总长度便可。直接上代码：
#include<iostream>
using namespace std;
/* 线段树求线段覆盖长度 */
#define BORDER 100 // 设线段端点坐标不超过100
struct Node // 线段树
{
int left;
int right;
int isCover; // 标记是否被覆盖
}segTree[4*BORDER];
/* 构建线段树 根节点开始构建区间[lef,rig]的线段树*/
void construct(int index, int lef, int rig)
{
segTree[index].left = lef;
segTree[index].right = rig;
if(rig - 1 == lef) // 到单位1线段
{
segTree[index].isCover = 0;
return;
}
int mid = (lef+rig) >> 1;
construct((index<<1)+1, lef, mid);
construct((index<<1)+2, mid, rig); // 非mid+1，线段覆盖[mid,mid+1]
segTree[index].isCover = 0;
}
/* 插入线段[start,end]到线段树, 同时标记覆盖 */
void insert(int index, int start, int end)
{
if(segTree[index].isCover == 1) return; // 如已覆盖，没必要继续向下插
if(segTree[index].left == start && segTree[index].right == end)
{
segTree[index].isCover = 1;
return;
}
int mid = (segTree[index].left + segTree[index].right) >> 1;
if(end <= mid)
{
insert((index<<1)+1, start, end);
}else if(start >= mid) // 勿漏=
{
insert((index<<1)+2, start, end);
}else
{
insert((index<<1)+1, start, mid);
insert((index<<1)+2, mid, end);
// 注：不是mid+1，线段覆盖，不能漏[mid,mid+1]
}
}
/* 计算线段覆盖长度 */
int Count(int index)
{
if(segTree[index].isCover == 1)
{
return segTree[index].right - segTree[index].left;
}else if(segTree[index].right - segTree[index].left == 1)
{
return 0;
}
return Count((index<<1)+1) + Count((index<<1)+2);
}
/* 测试线段 answer: 71 */
int segment[10][2] = {
5, 8, 10, 45, 0, 7,
2, 3, 3, 9, 13, 26,
15, 38, 50, 67, 39, 42,
70, 80
};
void main()
{
construct(0,0,100); // 构建[0,100]线段树
for(int i = 0; i < 10; ++i) // 插入测试线段
{
insert(0,segment[i][0],segment[i][1]);
}
printf("the cover length is %d
", Count(0));
}
总结：
基于排序的方法，由于排序的缘故，复杂度为O(nlgn)；使用线段树时，因其查询和插入操作都可以在lgn的时间完成，故对于所有线段完成插入，最后查询长度，算法总的复杂度也是O(nlgn)级别。
参考：线段覆盖长度 - 花开无言 - CSDN博客
https://blog.csdn.net/wwj_ff/article/details/48158169