高分求一算法

Question

有一些数据段，首尾两个数标识（它们不重复，排序的）：
(10,23),(34,49),(68,90)....现在给一个数据段(x,y)，求不与上面所有数据段重叠的集合。如：(x,y)=(7,40)，则不重叠段的集合为:
(7,9),(24,33)

Answer 1

有一组数据片断，它们只记录了起始和结束数(它们不重复不重叠，是排序的）。比如：(10,20)、(30,40)、(45,50)...(a,b)表示这个片断是从a开始到b结束。现在给一个开始数和结束数，求与这组片断不重叠的信息。比如：开始数为5,结束数为35.则与上面那组片断不重叠的信息是5-9,21-29。或者表示为(5,9),(21,29).

Answer 2

数据排序：10 20 30 40 45 50
数据下标： 0  1  2  3  4  5
对下标来说：n与n+1(n为偶数)对应的数及它俩之间的数为数据片断中的数。若要找开始数为5经束数为35且不与上重叠的信息，则重新排序：
数据排序：5 10 20 30 35 40 45 50
数据下标：0  1  2  3  4  5  6  7
那么所求则为：下标在0（对应数5）至4（对应数35），下标n与n+1(n为偶数)对应数之间的数为所求。所以所求下标为（0,1）、（2,3），所求对应的数则为（5,10）及（20,30）。又在上例中：要找(15,46)之间的数。
数据排序：10 15 20 30 40 45 46 50
数据下标： 0  1  2  3  4  5  6  7 
那么所求则为：下标在1（对应数15）至6（对应数46），下标n与n+1(n为偶数)对应数之间的数。所求下标为（2,3）、（4,5），所求对应数为（20,30）、（40,45）。

Answer 3

int array[20][2];
void show(int nstart,int nend)
{
  int i;
  for(i=0;i<20;i++)
  {
    if(array[i][0]>nstart || array[i][1]>=nstart)
      break;
  }
  int k;
  for(k=i;k<20;k++)
  {
     if(array[i][0]>nend || array[i][1]>=nend)
      break;
  }
  if(i==k)
  {
     if(array[i][0]>nstart)
     {
        printf("不重叠的信息是(%d,%d)",nstart,array[i][0]-1);
        return;
     }
     printf("没有不重叠的信息");
     return;
  }
  if(array[i][0]>nstart)
  {
     printf("不重叠的信息是(%d,%d)",nstart,array[i][0]-1);
     if(array[k][0]>nend)
     {
        for(int j=i;i<k-1;i++)
          printf("(%d,%d)",array[j][1]+1,array[j+1][0]-1);
        printf("(%d,%d)",array[j][1]+1,nend);
     }
     else
     {
        for(int j=i;i<k;i++)
          printf("(%d,%d)",array[j][1]+1,array[j+1][0]-1);
     }
  }
  else
  {
     if(array[k][0]>nend)
     {
        for(int j=i;i<k-1;i++)
          printf("(%d,%d)",array[j][1]+1,array[j+1][0]-1);
        printf("(%d,%d)",array[j][1]+1,nend);
     }
     else
     {
        for(int j=i;i<k;i++)
          printf("(%d,%d)",array[j][1]+1,array[j+1][0]-1);
     }
  }
}

Answer 4

谢谢大家的出谋划策最后的结果如下，数据片断也就日期片断void* CalcOverlapPart(int nBeginDate,int nEndDate)
{
int nBeginIndex=0;//开始日期处于第nBeginIndex片断中或之前
//==m_arrParts.GetSize()表是开始日期大于最后一
//个片断的结束日期。

int nEndIndex=-1;//结束日期处于nEndIndex片断中或之后.
//-1表示结束日期小于第一个片段的开始日期

//寻找nBeginIndex
while(nHead<=nEnd)
{
nMid=(nHead+nEnd)/2;
pPart=m_arrParts.GetAt(nMid);
if(pPart->m_nBeginDate>nBeginDate)
{
nEnd=nMid-1;
if(nEnd<nHead)
{
nBeginIndex=nMid;
}
}
else if(pPart->m_nEndDate<nBeginDate)
{
nHead=nMid+1;
if(nHead>nEnd)
{
nBeginIndex=nHead;
}
}
else
{
nBeginIndex=nMid;
break;
}

}


//寻找nEndIndex
nHead=0;
nEnd=m_arrParts.GetSize()-1;
while(nHead<=nEnd)
{
nMid=(nHead+nEnd)/2;
pPart=m_arrParts.GetAt(nMid);
if(pPart->m_nBeginDate>nEndDate)
{
nEnd=nMid-1;
if(nEnd<nHead)
{
nEndIndex=nMid-1;
}
}
else if(pPart->m_nEndDate<nEndDate)
{
nHead=nMid+1;
if(nHead>nEnd)
{
nEndIndex=nMid;
}
}
else
{
nEndIndex=nMid;
break;
}

}

if(nBeginIndex==(nEndIndex+1))
{
//无重叠，取日期段中的全部数据
}
else
{
COleDateTimeSpan DateSpan;
for(int i=nBeginIndex;i<=nEndIndex;i++)
{
pPart=this->m_arrParts.GetAt(i);
if((i==nBeginIndex)&&
(pPart->m_nBeginDate>nBeginDate))
{
//请求nBeginDate到pPart->m_nBeginDate-1之间的数据
}

if((i==nEndIndex)&&
(pPart->m_nEndDate<nEndDate))
{
//请求pPart->m_nEndDate-1到nEndDate之间的数据
}
if(i>nBeginIndex)
{
//第i-1片段与第i片段之间没相连部分)
}
}
}
}