题目：有两个有序的集合，集合的每个元素都是一段范围，求其交集，例如集合A：{[4,8],[9,13]} 和 集合B：{[6,12]}的交集为 {[6,8],[9,12]}
 
c语言实现:
 
#include <stdio.h>


 typedef struct sec_tag
 {
 double start;
 double end;
 } sec;


 #define min(a,b) (((a)<(b))?(a):(b))
 #define max(a,b) (((a)>(b))?(a):(b))


 //0表成功，非0表失败
 int intersec(sec s1,sec s2,sec *res);
 //len:数组长度，prefix_info:输出数字前要输出的字符串，presion小数点后保留位数
 void printout(sec *pset,int len,char* prefix_info,int presion);


 int main()
 {
 sec set1[4]={{6,8},
 {9,23},
 {25,27},
 {29,48}
 };
 sec set2[5]={{7,10},
 {11,15},
 {17,33},
 {35,39},
 {42,50}
 };
 sec set3[9]={0}; //存放取交集的结果
   sec sec1,sec2,sec3;
 int index1=0;
 int index2=0;
 int index3=0;
 int err=0;


 do 
 {
 sec1=set1[index1];
 sec2=set2[index2];
 err=intersec(sec1,sec2,&sec3);
 if(err<0)
 {
 index1++;
 }
 else if(err==0)
 {
 set3[index3]=sec3;
 index3++;
 if(sec3.end==sec1.end)
 index1++;
 else //if(sec3.end==sec2.end)
 index2++;
 }
 else if(err>0)
 {
 index2++;
 }
 } while(index1<4 && index2<5);
 printout(set1,4,"集合1:\t\t",0);
 printout(set2,5,"集合2:\t\t",0);
 printout(set3,9,"求交集的结果:\t",0);
 getchar();
 }


 //0表成功，非0表失败
 int intersec(sec s1,sec s2,sec *res)
 {
 res->start=res->end=0;
 if(s1.end<=s2.start) //s1在s2的左边，没有交集
 return -1;
 if(s1.start>=s2.end) //s1在s2的右边，没有交集
 return 1;
 res->start=max(s1.start,s2.start);
 res->end=min(s1.end,s2.end);
 return 0;
 }


 //len:数组长度，prefix_info:输出数字前要输出的字符串，presion小数点后保留位数
 void printout(sec *pset,int len,char* prefix_info,int presion)
 {
 int i=0;
 char format[20]="{%f,%f}\t";


 if(prefix_info!=NULL)
 printf("%s",prefix_info);


 if(presion>=0)
 sprintf(format,"{%%.%df,%%.%df}\t",presion,presion);


 for(;i<len;i++)
 {
 printf(format,pset[i].start,pset[i].end);
 }
 printf("\n");
 }

      博主遇​​到一个问题，要对文章根据用户阅读记录进行去重，但用户阅读记录的文章ID最长可以达到300条，然后在数据库中使用NOT  IN语句在查询时对文章进行去重，但是这样操作在记录比较长时，语句执行效率极其低下，
 
       最终博主想到了一个优化策略，在redis中缓存用户阅读的文章ID区间(文章ID是递增方式存入数据库)取代之间对文章ID校验去重的方式进行去重，这时就涉及到对用户的阅读文章ID区间进行求交集的操作，具体求交集思路见代码：
 
import java.util.*;


public class Main {

    public static boolean union(Set<String> set) {
        /*求并集  每次将两个可并集的区间合并*/
        Iterator<String> it = set.iterator();
        while (it.hasNext()) {
            String old = it.next();
            String[] arr = old.split(",");
            Iterator<String> it2 = set.iterator();
            while (it2.hasNext()) {
                String newstr = it2.next();
                String[] arr2 = newstr.split(",");
                if (!(arr[0].equals(arr2[0]) && arr[1].equals(arr2[1]))) {
                    //标记是否被合并
                    boolean isRemove = false;
                    //是否两个区间有交集 思路：如果没交集 区间二一定在区间一两边
                    if ((Long.parseLong(arr2[1]) - Long.parseLong(arr[0])) > -1 && (Long.parseLong(arr2[0]) - Long.parseLong(arr[1])) < 1) {
                        //如果区间一的终点小于区间二的终点 将区间二的终点代替区间一的终点
                        if (Long.parseLong(arr[1]) < Long.parseLong(arr2[1])) {
                            arr[1] = arr2[1];
                            isRemove = true;
                        }
                        //如果区间一的起点大于区间二的起点 将区间二的起点代替区间一的起点
                        if (Long.parseLong(arr[0]) > Long.parseLong(arr2[0])) {
                            arr[0] = arr2[0];
                            isRemove = true;
                        }
                        set.remove(newstr);
                        if (isRemove) {
                            //如果区间一的值被改变 修改区间一
                            set.remove(old);
                            set.add(arr[0] + "," + arr[1]);
                        }
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
      /*测试运行效率*/
        Random random = new Random();
        Set<String> set = new HashSet<String>();
        for (int i = 0; i < 100000; i++) {
            String insStr = "";
            int num = random.nextInt(10000000);
            insStr = random.nextInt(num) + "," + num;
            set.add(insStr);
        }
        /*测试准确性*/
        set.add("0,15");
        set.add("8,15");
        set.add("6,7");
        set.add("100,150");
        set.add("12,85");
        set.add("4,10");
        set.add("5,16");

        System.out.println("0.0 " + new Date().getTime());
        while (union(set)) {
        }
        System.out.println("-.- " + new Date().getTime());
        Iterator<String> it = set.iterator();
        while (it.hasNext()) {
            System.out.println(it.next().toString());
        }
}
 
优化代码：后期博主需要获取最大值 并对过小的值进行合并整合  故而优化方法如下（该优化弃用） ；
 
/**
     * 合并所有集合 并返回最大值
     * @param set
     * @param max
     * @return
     */
    public static Long union(Set<String> set ,Long max) {
        /*求并集  每次将两个可并集的区间合并*/
        Iterator<String> it = set.iterator();
        while (it.hasNext()) {
            String old = it.next();
            String[] arr = old.split(",");
            Iterator<String> it2 = set.iterator();
            if (Long.parseLong(arr[1]) > max) {
                max = Long.parseLong(arr[1]);
            }
            while (it2.hasNext()) {
                String newstr = it2.next();
                String[] arr2 = newstr.split(",");
                if (!(arr[0].equals(arr2[0]) && arr[1].equals(arr2[1]))) {
                    //标记是否被合并
                    boolean isRemove = false;
                    //是否两个区间有交集 思路：如果没交集 区间二一定在区间一两边
                    if ((Long.parseLong(arr2[1]) - Long.parseLong(arr[0])) > -1 && (Long.parseLong(arr2[0]) - Long.parseLong(arr[1])) < 1) {
                        //如果区间一的终点小于区间二的终点 将区间二的终点代替区间一的终点
                        if (Long.parseLong(arr[1]) < Long.parseLong(arr2[1])) {
                            arr[1] = arr2[1];
                            isRemove = true;
                        }
                        //如果区间一的起点大于区间二的起点 将区间二的起点代替区间一的起点
                        if (Long.parseLong(arr[0]) > Long.parseLong(arr2[0])) {
                            arr[0] = arr2[0];
                            isRemove = true;
                        }
                        set.remove(newstr);
                        if (isRemove) {
                            //如果区间一的值被改变 修改区间一
                            set.remove(old);
                            set.add(arr[0] + "," + arr[1]);
                        }
                        max = union(set , max);
                        return max;
                    }
                }
            }
        }
        return max;
    }
 
博主对上面的代码进行大数据（10W+区间）测试后，发现会出现堆栈错误，递归调用太多，线程池满了；
 
重新优化代码后 耦合度增加  但减少运算次数
 
import java.util.*;


public class Main {

    /**
     * 合并所有集合 并返回最大值
     *
     * @param set
     * @param max
     * @return
     */
    public static Long union(Set<String> set, Long max) {
        /*求并集  每次将两个可并集的区间合并*/
        Iterator<String> it = set.iterator();
        while (it.hasNext()) {
            String old = it.next();
            String[] arr = old.split(",");
            Iterator<String> it2 = set.iterator();
            if (Long.parseLong(arr[1]) > max) {
                max = Long.parseLong(arr[1]);
            }
            while (it2.hasNext()) {
                String newstr = it2.next();
                String[] arr2 = newstr.split(",");
                if (!(arr[0].equals(arr2[0]) && arr[1].equals(arr2[1]))) {
                    //标记是否被合并
                    boolean isRemove = false;
                    //是否两个区间有交集 思路：如果没交集 区间二一定在区间一两边
                    if ((Long.parseLong(arr2[1]) - Long.parseLong(arr[0])) > -1 && (Long.parseLong(arr2[0]) - Long.parseLong(arr[1])) < 1) {
                        //如果区间一的终点小于区间二的终点 将区间二的终点代替区间一的终点
                        if (Long.parseLong(arr[1]) < Long.parseLong(arr2[1])) {
                            arr[1] = arr2[1];
                            isRemove = true;
                        }
                        //如果区间一的起点大于区间二的起点 将区间二的起点代替区间一的起点
                        if (Long.parseLong(arr[0]) > Long.parseLong(arr2[0])) {
                            arr[0] = arr2[0];
                            isRemove = true;
                        }
                        set.remove(newstr);
                        if (isRemove) {
                            //如果区间一的值被改变 修改区间一
                            set.remove(old);
                            set.add(arr[0] + "," + arr[1]);
                        }
//                        max = union(set , max);
                        return max;
                    }
                }
            }
        }
        return -1L;
    }

    public static void removeSmall(Set<String> set) {
        Iterator<String> it = set.iterator();
        Long min = 0L;
        Long max = 0L;
        while (it.hasNext()) {

        }
    }

    public static void main(String[] args) {
        /*测试运行效率*/
        Random random = new Random();
        Set<String> set = new HashSet<String>();
        for (int i = 0; i < 100000; i++) {
            String insStr = "";
            int num = random.nextInt(10000000);
            insStr = random.nextInt(num) + "," + num;
            set.add(insStr);
        }
        /*测试准确性*/
        set.add("0,15");
        set.add("8,15");
        set.add("6,7");
        set.add("100,200");
        set.add("12,85");
        set.add("4,10");
        set.add("5,16");

        System.out.println("0.0 " + new Date().getTime());
        Long max = 0L;
        for(Long tempMax=max; (tempMax = union(set, max)) >= 0 ; )
        {
            max = tempMax;
        }
        System.out.println("MAX = " + max);
        System.out.println("-.- " + new Date().getTime());
        Iterator<String> it = set.iterator();
        while (it.hasNext()) {
            System.out.println(it.next().toString());
        }
    }
}
 
 

题目描述：有两个有序的集合，集合的每个元素都是一段范围，求其交集，例如集合{[4,8],[9,13]}和{[6,12]}的交集为{[6,8],[9,12]}。
 
我们知道，两个集合的交集必定是去满足范围小的那个集合，因此此题的解法就是每次寻找一个小的范围。那么，关键之处就在于如何寻找这个范围。
 
如下图所示，两个集合{[2,8],[9,14]}和{[1,10],[12,15]}：
 
 
 

  
  
 
 
集合从左到右进行扫描，每次选取边界的时候都是去选取值小的边界，假设两个数组的索引分别为i和j并指向起始位置。
 
1<2，选1，索引j向后移动，此时i指向2，j指向10；
2<10，选2，索引i向后移动，此时i指向8，j指向10；
8<10，选8，找到一个右边界，[2，8]为其中一个结果，索引i向后移动，此时i指向9，j指向10；
以此类推……
 
那么，什么时候确定为一个结果子集呢？
 
由于扫描为从左到右扫描，开始扫描的时左边界，每次总是取边界中值较小的边界，我们要去寻找一个右边界，因此达到一左一右的状态时，即为一个结果子集。但是，这里有一个重要的地方就是判断结果是否正确。比如上面的例子中，选择1之后的索引达到了一左一右的状态，但是[2，10]并不是我们想要的。在我们选2之后，选8之前，i和j分别指向8和10，即在确定右边界之前，必定要达到两个集合的索引同时达到右边界，然后对两个右边界加以判断。因此需要加一个标志，去判断确定右边界之前是否同时达到右边界。
 
public class SetIntersection {

	private void intersection(int[] a, int[] b) {
		int len1 = a.length, len2 = b.length;
		int flag = 0, i = 0, j = 0;
		int pre1 = 0, pre2 = 0;
		while (i < len1 && j < len2) {
			pre2 = pre1;
			if (i % 2 == 1 && j % 2 == 1) {
				flag = 1;
			} else {
				flag = 0;
			}
			if (a[i] < b[j]) {
				pre1 = a[i++];
			} else {
				pre1 = b[j++];
			}
			if (flag == 1 && ((i % 2 == 0 && j % 2 == 1) || (i % 2 == 1 && j % 2 == 0))) {
				System.out.println(pre2 + " " + pre1);
			}
		}
	}

	public static void main(String[] args) {
		int a[] = { 2, 8, 9, 14, 15, 20, 22, 25 };
		int b[] = { 1, 10, 12, 16, 19, 25, 30, 40 };
		new SetIntersection().intersection(a, b);
	}
}
 
这里我们将两个集合的边界有序地放到了数组里面，下面是程序的输出结果。
 
 
有兴趣的朋友可以自己试着改进一下我的算法。
 
 
 
 
 
 
 
 

如下所示：
 
                                        1      3        4                    9             11            13
 
n1段区间之间互无交集，|——|        |——————|               |————|                                         
 
n2段区间之间互无交集       |————|     |——|   |————|              |——————|
 
 
                                            2            5     6     7   8            10           12                  14
 
仅通过图示来看很容易得到交集的答案，交集是[2,3], [4,5],  [6,7],  [8,9],  [12,13]，但是当区间很多时如何去求？
 

 
 
首先定义两个List<Long> list1=new ArrayList<Long>();   List<Long> list2=new ArrayList<Long>();
 
list1放置n1段区间的起始终止点 ：list1.add(1);list1.add(3);...
 
list2放置n2段区间的起始终止点：list2.add(2);list2.add(5);.....
 
 
然后调用函数：
 

public List<Long> GetIntersection(List<Long> list1, List<Long> list2){
		List<Long> intersection=new ArrayList<Long>();
		
		for(int i=0;i<list1.size();i+=2){
			Long start1=list1.get(i);  Long end1=list1.get(i+1);
			for(int j=0;j<list2.size();j+=2){
				Long start2=list2.get(j);  Long end2=list2.get(j+1);
				//  |______|                                   |______|
				//             |______|     or        |______|
				if(end1<=start2 || end2<=start1){continue;}
				if(start2>start1){				    
					if(end1<end2){
					    //  |______|
						//       |______|
						intersection.add(start2);  intersection.add(end1);						
					}else{
						//  |______|
						//    |____|
						intersection.add(start2);  intersection.add(end2);	
					}
				}else{
					if(end1<end2){
					    //      |___|
						//     |______|
						intersection.add(start1);  intersection.add(end1);						
					}else{
						//       |______|
						//    |____|
						intersection.add(start1);  intersection.add(end2);	
					}
				}
			}
		}
		return intersection;
	}