【 亿级数据 】求 A中不存在B 的区间 高效算法,该怎么处理

【 亿级数据 】求 A中不存在B 的区间 高效算法
闭区间 排好序了的  递增

———————A———————————-- 
[2,10]
[11,30]
[35,48]
[49,50]
[54,70]
[73,100]
几十万个区间   [m,n]  n最大值为几十亿的了


———————B———————————--
[1,8]
[10,20]
[21,30]
[32,48]
[49,50]
[51,66]
[69,121]
几十万个区间   [m,n]  n最大值为几十亿的了


—————找 A中不存在B 的区间 ——结果如下：—————————————————---

[1,1]
[32,34]
[51,53]
[71,72]
[101,121]

注：如果 几十亿一个个枚举的话 cpu 和内存 不够！
    A B 区间 各有 几十万，区间数量不一定相等！

所以只能求高效算法 
 
------解决方案--------------------
既然排好序了从小到大比较不就得了，O（N）的复杂度还不够？
------解决方案--------------------
这个跟n的大小没关系啊，复杂度只跟区间个数有关
------解决方案--------------------
如果数据量很大的话，不可能一次读到内存中。
可以一次读取一部分数据，而且区间是排好序，然后一个个计算A和B的区间不就可以了吗。

------解决方案--------------------
读一行，判断一行的，不需要全部读进来。
------解决方案--------------------
数据放在A.txt和B.txt
结果写入C.txt

#include <iostream>

#include <fstream>


using std::pair;

using std::ifstream;

using std::ofstream;

typedef pair<unsigned int, unsigned int> Upair;


inline unsigned Min(unsigned int x, unsigned int y) {return x < y ? x : y;}

inline unsigned Max(unsigned int x, unsigned int y) {return x > y ? x : y;}

ifstream& getpairfromfile(ifstream& ifs, Upair& inoutpair);

Upair left(Upair& uall, const Upair& ua);


int main()

{

	ifstream inA("A.txt");

	ifstream inB("B.txt");

	ofstream outC("C.txt");


	Upair upa, upb(0, 0), upc, upall(1, -1);

	//设置b(0,0)是为了第一次去读b

	//c是当前处理的区间

	//all是整个正整数区间

	while (inB)

	{

		if (inA)  //A文件没读完，要分区，否则直接把剩余的区间作为当前区间

		{

			getpairfromfile(inA, upa);

			upc = left(upall, upa);

		}

		else

			upc = upall;


		while (inB && upc.second >= upb.second && upc.first <= upc.second)  

                //当前区间还有空间而且右边界比B区间大，否则去读A文件继续划分区间

		{	

			while(inB && upc.first > upb.second) //B区间在当前区间的左边

			{

				getpairfromfile(inB, upb);    //读取B区间

			}

			if (!inB)

				break;


			//计算当前区间和B区间重复的部分，并写入c文件

			unsigned int low, high;

			low = Max(upc.first, upb.first);

			high = Min(upc.second, upb.second);

			outC << '[' << low << ',' << high << ']' << std::endl;

			upc.first = high + 1; //当前区间左边界重新计算

		}

	}


	inA.close();

	inB.close();

	outC.close();

	printf("done.\n");

	return 0;

}


ifstream& getpairfromfile(ifstream& ifs, Upair& inoutpair)

{

	//读文件一行，取得区间

	char buff[128];

	ifs.getline(buff, 128);

	sscanf(buff, "[%u,%u]", &inoutpair.first, &inoutpair.second);

	return ifs;

}


Upair left(Upair& uall, const Upair& ua)

{

	//把整个区间根据A的区间分成2部分

	Upair ret;

	ret.first = uall.first;

	ret.second = ua.first - 1;

	uall.first = ua.second + 1;

	return ret;

}

A.txt

[2,10]

[11,30]

[35,48]

[49,50]

[54,70]

[73,100]

B.txt

[1,8]

[10,20]

[21,30]

[32,48]

[49,50]

[51,66]

[69,121]

处理结果 C.txt

[1,1]

[32,34]

[51,53]

[71,72]

[101,121]