学步园

http://haixiaoyang.wordpress.com/category/intervalsegment/

//None overlap segments (5,10)(15,17)(18,25), 
//insert (16,35), print out merged result:（5，10）（15，35）

void PrintMergRes(int a[], int b[], int n, int nBeg, int nEnd)
{
	assert(a && b && n > 0 && nBeg < nEnd);

	int i = 0;
	bool bPrinted = false;
	while (i < n)
	{
		if (a[i] > nEnd && !bPrinted)
		{
			cout<<"("<<nBeg<<" "<<nEnd<<")"<<endl;
			bPrinted = true;
		}
		else
		{
			if (max(nBeg, a[i]) <= min(nEnd, b[i]))
			{
				nBeg = min(nBeg, a[i]);
				nEnd = max(nEnd, b[i]);
			}
			else 
				cout<<"("<<a[i]<<" "<<b[i]<<")"<<endl;
			i++;
		}
	}

	//falls after all intervals
	if (!bPrinted) 
		cout<<"("<<nBeg<<" "<<nEnd<<")"<<endl;
}

看似很简单的题目，但是要优美正确的写出来，还是需要一定功夫的

/*
Given two arrays storing ranges(none overlap), output their intersection.
Input:
A: [1,5], [8,15], [30,90]
B: [2,7], [12,18], [80,100]
Output:
[2,5], [12,15], [80,90]
*/

struct RANGE
{
	int nBeg;
	int nEnd;
};

void PrintIntersect(RANGE rg1[], int n1, RANGE rg2[], int n2)
{
	assert(rg1 && rg2 && n1 > 0 && n2 > 0);

	//Typical merge sort logic without a think
	int nIter1 = 0;
	int nIter2 = 0;
	while (nIter1 < n1 && nIter2 < n2)
	{
		//This logic below is the way to judge whether two segment
		//intersect with each other. Double think why!!
		int nMaxBeg = max(rg1[nIter1].nBeg, rg2[nIter2].nBeg);
		int nMinEnd = min(rg1[nIter1].nEnd, rg2[nIter2].nEnd);
		if (nMinEnd >= nMaxBeg)
			cout<<nMaxBeg<<" "<<nMinEnd<<endl;

		if (rg1[nIter1].nEnd <= rg2[nIter2].nEnd)
			nIter1++;
		else nIter2++;
	}
}