小张经常为了事情太多安排不开而苦恼。现在他手头有 n 项任务,每项任务都有一个开始时间 s_i 和结束时间 e_i 。要想完成一个任务必须从开始时间做到结束时间,并且同一时间小张只能进行一项任务。
小张想知道他最多可以完成几项任务。
Input
第一行一个整数 n(1 \leq n \leq 300000 ) ,表示小张手头任务的个数。
接下来 n 行,每行两个整数 s_i,e_i(1 \leq s_i < e_i \leq 10^9 ) ,表示任务的开始时间和结束时间。
Output
一行一个整数,表示小张最多可以完成几项任务。
问题貌似在ver_count里面:
#include <stdio.h>
#include <stdlib.h>
int ans=0;
int start[300030],end[300030];
void ver_count(int a[],int b[],int l,int m,int r)
{
int k=0,i=l,j=m+1;
int *temp1 = (int *)malloc((r-l+1)*sizeof(int)),*temp2 = (int *)malloc((r-l+1)*sizeof(int));
while (i <= m && j <= r)
{
if(b[i]<=b[j])
{
temp2[k]=b[i];
temp1[k]=a[i];
k++;i++;
}
else
{
temp2[k]=b[j];
temp1[k]=a[j];
k++;j++;
}
}
while(i<=m)
{
temp2[k]=b[i];
temp1[k]=a[i];
k++;i++;
}
while(j<=r)
{
temp1[k]=a[j];
temp2[k]=b[j];
k++;j++;
}
for(int s=0;s<k;s++)
{
a[l+s]=temp1[s];
b[l+s]=temp2[s];
}
free(temp1);
free(temp2);
}
void merge(int a[],int b[],int left,int right)
{
if(left==right) return;
int middle=(left+right)/2;
merge(a, b, left, middle);
merge(a, b, middle+1, right);
ver_count(a, b, left, middle, right);
}
int main()
{
int n=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d %d",&start[i],&end[i]);
}
merge(start, end, 0, n-1);
int *p=NULL,*q=NULL,flag=1;
p=end;q=start+1;
while((p<=end+n-1)&&(q<=start+n))
{
if(*p<=*q)
{
ans++;
p+=flag;q++;
flag=1;
}
else {
q++;
flag++;
}
}
printf("%d\n",ans+1);
return 0;
}