Pagini recente » Cod sursa (job #2405211) | Cod sursa (job #1241545) | Cod sursa (job #1723042) | Cod sursa (job #3214232) | Cod sursa (job #1206016)
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX 100005
struct interval
{
int st, dr;
};
interval v[MAX];
int k[MAX], sol[MAX];
bool comp(interval a, interval b)
{
if(a.st == b.st)
return a.dr > b.dr;
return a.st < b.st;
}
bool comp2(int a, int b)
{
return a > b;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int n, i, R, L;
scanf("%d",&n);
for(i=1; i<=n; i++)
scanf("%d%d",&v[i].st,&v[i].dr);
sort(v+1,v+n+1,comp);
int *poz;
int u=0, el;
for(i=1; i<=n; i++)
{
poz = lower_bound(k+1,k+u+1,v[i].st, comp2);
el = (int)(poz-k);
if(el >= u)
u++;
k[el] = v[i].dr;
sol[el] += v[i].dr-v[i].st;
}
printf("%d",sol[1]);
return 0;
}