# 11992: 【原1992】绮礼的阴谋

### 题目描述

author: Weihao Kong 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1992

## 题目描述

Assassin每份灵体的能力不同。 第$$i$$份灵体可以监视到的区域是闭区间$$[a_i,b_i]$$。

## 样例输入

3
3959 21659
8666 26551
3392 11450


## 样例输入

23159


## 样例解释

$$[3959,21659]\cup[8666,26551]\cup[3392,11450] = [3392,26551]$$

## BugenZhao's solution

//
// Created by BugenZhao on 2019/3/23.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

using ll=long long;

/*class Interval {
public :
int l;
int r;

bool operator<(const Interval &rhs) const {
if (l < rhs.l)
return true;
if (rhs.l < l)
return false;
return r < rhs.r;
}
};*/

int main() {
int starts[10005], ends[10005];
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
scanf("%d%d", &starts[i], &ends[i]);
}

sort(starts, starts + n);
sort(ends, ends + n);

int length = 0;
int i = 0, j = 0;
for (; i < n; ++i) {
if (i == n - 1 || starts[i + 1] > ends[i]) {
length += ends[i] - starts[j];
j = i + 1;
}
}
cout << length << endl;
return 0;
}


## FineArtz's solution

/* 绮礼的阴谋 */
#include <iostream>
#include <algorithm>
using namespace std;

class Interval{
public:
//constructor
Interval() : l(0), r(0) {}
Interval(int x, int y) : l(x), r(y) {}
Interval(const Interval &i) : l(i.l), r(i.r) {}

int l, r;
};
inline bool cmp(Interval i1, Interval i2){
return (i1.l < i2.l || i1.l == i2.l && i1.r > i2.r);
}

int main(){
int n;
cin >> n;
Interval a[10005];
for (int i = 0; i < n; ++i)
cin >> a[i].l >> a[i].r;
sort(a, a + n, cmp);
/*for (int i = 0; i < n; ++i)
cout << a[i].l << ' ' << a[i].r << endl;*/
long long nowl = a[0].l, nowr = a[0].r;
long long ans = 0;
for (int i = 1; i < n; ++i){
if (nowl <= a[i].l && a[i].l <= nowr){
if (nowr < a[i].r) nowr = a[i].r;
}
else{
ans += nowr - nowl;
nowl = a[i].l;
nowr = a[i].r;
}
}
ans += nowr - nowl;
cout << ans << endl;
return 0;
}


## ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

int times[10009][2] = { 0 };

template <class T>
void quick_sort(T start, T end) {
if (start == end)
return;
auto i = start, j = end;
--j;
if (i == j)
return;
//交换
auto key = (*start)[0];
auto tmp = (*start)[1];
for (bool status = true; i != j;) {
if (status) {
if ((*j)[0] < key) {
(*i)[0] = (*j)[0];
(*i)[1] = (*j)[1];
++i;
status = false;
}
else
--j;
}
else {
if ((*i)[0] > key) {
(*j)[0] = (*i)[0];
(*j)[1] = (*i)[1];
--j;
status = true;
}
else
++i;
}
}
(*i)[1] = tmp;
(*i)[0] = key;
//递归
quick_sort(start, i + 1);
quick_sort(i + 1, end);
}

int main() {
int n;
cin >> n;

for (int i = 0; i < n; ++i) {
scanf("%d %d", &times[i][0], &times[i][1]);
}
quick_sort(times, times + n);

int ans = 0;
int cur_left = 0, cur_right = 0;
for (int i = 0; i < n; ++i) {
if (times[i][0] > cur_right) {
ans += cur_right - cur_left;
cur_left = times[i][0];
cur_right = times[i][1];
}
else {
if (cur_right < times[i][1])
cur_right = times[i][1];
}
}
ans += cur_right - cur_left;

cout << ans;

return 0;
}


## skyzh's solution

#include <iostream>
#include <algorithm>
using namespace std;

struct Range {
int L, R;
} R[10000];

bool cmp(const Range& a, const Range& b) {
return a.L <= b.L;
}

int main() {
long long SUM = 0;
int N;
cin >> N;
for (int i = 0; i < N; i++) cin >> R[i].L >> R[i].R;
sort(R, R + N, cmp);
int LS = R[0].L, LE = R[0].R;
for (int i = 1; i < N; i++) {
if (R[i].L > LE) {
SUM += (long long) LE - LS;
LE = R[i].R;
LS = R[i].L;
} else if (R[i].R > LE) {
LE = R[i].R;
}
}
SUM += (long long) LE - LS;
cout << SUM << endl;
return 0;
}


## yyong119's solution

#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAX_N 10010
using namespace std;

struct node{
int l, r;
} a[MAX_N];
int n, cnt;

inline bool cmp(node p, node q) {
return p.l < q.l;
}

int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%d%d", &a[i].l, &a[i].r);
sort(a, a + n, cmp);
int upd = 0, cur_l = a[0].l, cur_r = a[0].r;
for (int i = 1; i < n; ++i) {
if (a[i].r <= cur_r) continue;
if (a[i].l > cur_r) {
cnt += cur_r - cur_l;
cur_l = a[i].l;
}
cur_r = a[i].r;
}
cnt += cur_r - cur_l;
printf("%d\n", cnt);
return 0;
}