大米实习笔试题

题目：一条直线有n条线段，例如[1,9] 和 [5,10]两条线段，则说线段的覆盖范围为9，如果多重覆盖，则只计算一次，例如[1,9] 和 [2,8]两条线段，则说线段的覆盖范围为8，即[2,8]在[1,9]里面不再计算。大米给出的表示是

 class Segment{
		int start;
		int end;
	}

最直接的做法，先排序，后计算:

	// 插入排序
	public static void sort(Segment[] seg) {
		if (seg == null)
			return;
		//转换seg，保证每一个seg的start小于end
		for(int i=0;i<seg.length;i++){  
			if(seg[i].start>seg[i].end){
				int t = seg[i].start;
				seg[i].start = seg[i].end;
				seg[i].end = t;
			}
		}
		//插入排序
		for (int i = 1; i < seg.length; i++) {
			int tempStart = seg[i].start;
			int tempEnd = seg[i].end;
			int j = i - 1;
			while (j >= 0 && seg[j].start > tempStart) {
				seg[j + 1].start = seg[j].start;
				seg[j + 1].end = seg[j].end;
				j--;
			}
			seg[j + 1].start = tempStart;
			seg[j + 1].end = tempEnd;
		}
	}

下面计算覆盖数：

	//计算距离，seg为已经排好序的
	public static int seg(Segment[] seg){
		if(seg==null)return -1;
		if(seg.length==1)return seg[0].end-seg[0].start;
		int p = 0,q = 0, sum = 0; //p，q为标记线段的起始和终止位置，sum为计算的距离总和
		for(int i=1;i<seg.length;i++){
			if(seg[i].start>seg[q].end){ //如果选择的线段起始点大于终止点的end，则把p到q的距离先加起来
				sum+=(seg[q].end-seg[p].start);//然后至q和q等于新的i，这个时候i还没有加进sum
				p = i;
				q = i;
			}else{				//如果选择的线段start小于终止点的end，分两种情况
				if(seg[i].end>seg[q].end){ //1：如果选择的线段end大于终止点的end，则把i设置成新的
					q = i;					//2：如果选择的线段end小于终止点的end，什么都不做
				}
			}
		}
		sum += (seg[q].end-seg[p].start);  //最后要加上没有计算的pq
		return sum;
	}

测试数据：[1,9] [5,7] [2,10] [11,12]

得到的结果：10

测试数据：[11,9] [2,7] [2,10] [11,18]

得到的结果：16

测试数据：[-2,0] [3,7] [2,6] [19,18]

得到的结果：8

暂时只想到上面的解法，有更好的解法欢迎指教。