VC/c/c++ 如何求区间长度
如 区间 [1,2] ,[2,4],[3,6]
长度为6-1 = 5；
不考虑区间为半开半闭。
[解决办法]
我的思路：先排序（排序优先按照左区间数排），然后循环判断第i+1的左数是否在第i个区间内(i+1左 >= i左 && i+1左 <= i右)，如果不在，直接将第i区间保存，否则判断i+1右数是否在i区间内，若在就消除i+1区间（消除的意思是将来统计不处理他们）否则将第i区间变为（i左，i+1右）并保存；将保存的作为当前区间再和下一个同样比较处理。最后将整理出来的各个区间（肯定不重叠）分别的右-左相加就行了。
[解决办法]
仅供参考
//实现一个函数：求数轴上多个线段覆盖的区域对应的多个线段; 输入多个线段,求出被这些线段覆盖的所有区域(也用线段表示); 一条线段用两个值表示(x0,x1), 其中x1>x0;
//比如(1,3);(2,4);(5,6);结果为(1,4);(5,6);
//比如(1,3);(2,4);(5,6);(4,7);结果为(1,7);
#include <stdio.h>
#define MAXLINES 100
struct LINE {
int x0;//左端
int x1;//右端
} ls[MAXLINES];
int i,j,k,n,x0,x1,c;
void add() {
if (0==n) {//加入第一对点
ls[n].x0=x0;
ls[n].x1=x1;
n=1;
} else {
if (x1==ls[0].x0) {//右端＝第一条线段的左端
ls[0].x0=x0;//第一条线段的左端修改为左端
return;
}
if (x1<ls[0].x0) {//右端＜第一条线段的左端
for (i=n-1;i>=0;i--) {//将所有线段往后移
ls[i+1].x0=ls[i].x0;
ls[i+1].x1=ls[i].x1;
}
ls[0].x0=x0;//新第一条线段为x0,x1
ls[0].x1=x1;
n++;
return;
}
if (ls[n-1].x1<x0) {//左端＞最后那条线段的右端
ls[n].x0=x0;//新最后那条线段
ls[n].x1=x1;
n++;
return;
}
if (x0<=ls[0].x0 && ls[n-1].x1<=x1) {//左端≤第一条线段的左端且最后那条线段的右端≤右端
ls[0].x0=x0;//只剩这一条线段
ls[0].x1=x1;
n=1;
return;
}
for (i=0;i<n;i++) {//从左到右依次检查每条线段
if (ls[i].x0<=x0 && x0<=ls[i].x1) {//第i条线段的左端≤左端≤第i条线段的右端
for (j=i;j<n;j++) {//从第i条线段开始从左到右依次检查每条线段
if (ls[j].x0<=x1 && x1<=ls[j].x1) {//第j条线段的左端≤右端≤第j条线段的右端
ls[i].x1=ls[j].x1;//第i条线段的右端改为第j条线段的右端
for (k=1;k<=n-j-1;k++) {//将剩余线段往前移
ls[i+k].x0=ls[j+k].x0;
ls[i+k].x1=ls[j+k].x1;
}
n-=j-i;
return;
}
if (ls[j].x1<x1 && (j==n-1
[解决办法]
x1<ls[j+1].x0)) {//第j条线段的右端＜右端＜第j+1条线段的左端(如果有)
ls[i].x1=x1;//第i条线段的右端改为右端
for (k=1;k<=n-j-1;k++) {//将剩余线段往前移
ls[i+k].x0=ls[j+k].x0;
ls[i+k].x1=ls[j+k].x1;
}
n-=j-i;
return;
}
}
}
if (ls[i].x1<x0 && (i==n-1
[解决办法]
x0<ls[i+1].x0)) {//第i条线段的右端＜左端＜第i+1条线段的左端(如果有)
if (i!=n-1 && x1<ls[i+1].x0) {//右端＜第i+1条线段的左端(如果有)
for (k=n-1;k>=i+1;k--) {//将从第i+1条线段开始的所有线段往后移
ls[k+1].x0=ls[k].x0;
ls[k+1].x1=ls[k].x1;
}
ls[i+1].x0=x0;//新第i+1条线段为x0,x1
ls[i+1].x1=x1;
n++;
return;
}
for (j=i+1;j<n;j++) {//从第i+1条线段开始从左到右依次检查每条线段
if (ls[j].x0<=x1 && x1<=ls[j].x1) {//第j条线段的左端≤右端≤第j条线段的右端
ls[i+1].x0=x0;//第i+1条线段的左端改为左端
ls[i+1].x1=ls[j].x1;//第i+1条线段的右端改为第j条线段的右端
for (k=1;k<=n-j-1;k++) {//将剩余线段往前移
ls[i+1+k].x0=ls[j+k].x0;
ls[i+1+k].x1=ls[j+k].x1;
}
n-=j-i-1;
return;
}
if (ls[j].x1<x1 && (j==n-1
[解决办法]
x1<ls[j+1].x0)) {//第j条线段的右端＜右端＜第j+1条线段的左端(如果有)
ls[i+1].x0=x0;//第i+1条线段的左端改为左端
ls[i+1].x1=x1;//第i+1条线段的右端改为右端
for (k=1;k<n-j-1;k++) {//将剩余线段往前移
ls[i+k].x0=ls[j+k].x0;
ls[i+k].x1=ls[j+k].x1;
}
n-=j-i-1;
return;
}
}
}
if (x0<ls[i].x0) {//左端＜第i条线段的左端
for (j=i;j<n;j++) {//从第i条线段开始从左到右依次检查每条线段
if (ls[j].x0<=x1 && x1<=ls[j].x1) {//第j条线段的左端≤右端≤第j条线段的右端
ls[i].x0=x0;//第i条线段的左端改为左端
ls[i].x1=ls[j].x1;//第i条线段的右端改为第j条线段的右端
for (k=1;k<=n-j-1;k++) {//将剩余线段往前移
ls[i+k].x0=ls[j+k].x0;
ls[i+k].x1=ls[j+k].x1;
}
n-=j-i;
return;
}
if (ls[j].x1<x1 && (j==n-1
[解决办法]
x1<ls[j+1].x0)) {//第j条线段的右端＜右端＜第j+1条线段的左端(如果有)
ls[i].x0=x0;//第i条线段的左端改为左端
ls[i].x1=x1;//第i条线段的右端改为右端
for (k=1;k<=n-j-1;k++) {//将剩余线段往前移
ls[i+k].x0=ls[j+k].x0;
ls[i+k].x1=ls[j+k].x1;
}
n-=j-i;
return;
}
}
}
}
}
}
void show() {
for (i=0;i<n;i++) {
printf("(%d,%d);",ls[i].x0,ls[i].x1);
}
printf("\n");
}
void main() {
n=0;
c=0;
while (1) {
printf("Input x0,x1(x0<x1;0,0 to exit):");
fflush(stdout);
rewind(stdin);
if (2==scanf("%d,%d",&x0,&x1)) {
if (0==x0&&0==x1) break;
if (x1>x0) {
c++;
if (c>=MAXLINES) {
printf("Up to %d!\n",MAXLINES);
break;
}
add();
show();
}
}
}
}
