算法题：马路上的路灯<考察重复数据剔除>

题目：

思路：

1. 建立1到M+1的数组，0表示存在路灯，1表示移除路灯

2. 输入数据时：如100  200，则循环把100到200内的路灯标识为1，表示移除，这样做的好处是不用考虑下面的重复，下面即使有重复数据，也会覆盖为1；

3.输出为0的路灯个数即可。

import java.util.Scanner; public class case13 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int M=sc.nextInt(); int N =sc.nextInt(); int []total=new int[M+1];//自动初始化字段为0 for(int i=0;i<N;i++){ //把需要移除的值覆盖为1 int a= sc.nextInt(); int b=sc.nextInt(); for(int j=a;j<=b;j++){ total[j]=1; } } int count=0; for(int i=0;i<=M;i++){//统计个数 if(total[i]==0) count++; } System.out.println(count); } }

还有一种比较传统的比较思路：

1. 按照起始点的大小从小到大进行排序

2. 遍历：判断若 i+1个的起始点比i个的终点值小，则把i+1个的起始点设置为i的终点+1，依次类推；

3.把所有的距离断累加即可。