# 11360: 【原1360】偶像丁姐的烦恼

### 题目描述

author: SSY 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1360

## Sample Input

``````10
0 3
0 5
10 13
12 15
2 6
4 8
9 11
13 18
14 16
15 20
``````

## Sample Output

``````5
``````

## Hint

n≤100000

0≤t1_i＜t2_i≤1000000

## BugenZhao's solution

``````//
// Created by BugenZhao on 2019/3/17.
//
// 线段覆盖 右端点贪心

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

static const auto _____ = []() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
return nullptr;
}();

class Period {
public:
int a;
int b;

bool operator<(const Period &rhs) const {
if (b < rhs.b)
return true;
if (rhs.b < b)
return false;
return a < rhs.a;
}
};

int main() {
int n;
cin >> n;
auto periods = new Period[n];
for (int i = 0; i < n; ++i) {
cin >> periods[i].a;
cin >> periods[i].b;
}
sort(periods, periods + n);

int current = periods[0].b;
int count = 1;
for (int j = 1; j < n; ++j) {
if (periods[j].a >= current) {
++count;
current = periods[j].b;
}
}
cout << count << endl;
delete[] periods;
return 0;
}
``````

## ligongzzz's solution

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

int times[100009][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)[1];
auto tmp = (*start)[0];
for (bool status = true; i != j;) {
if (status) {
if ((*j)[1] < key) {
(*i)[0] = (*j)[0];
(*i)[1] = (*j)[1];
++i;
status = false;
}
else
--j;
}
else {
if ((*i)[1] > key) {
(*j)[0] = (*i)[0];
(*j)[1] = (*i)[1];
--j;
status = true;
}
else
++i;
}
}
(*i)[0] = tmp;
(*i)[1] = key;
//递归
quick_sort(start, i + 1);
quick_sort(i + 1, end);
}

int main() {
int n;
scanf("%d", &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;
for (int i = 0, cur_time = 0; i < n; ++i) {
if (times[i][0] >= cur_time) {
++ans;
cur_time = times[i][1];
}
}

cout << ans;

return 0;
}
``````

## q4x3's solution

``````/**
* 模拟
* 根据活动结束时间排序
* 结束最早的先安排上
* 再看第二早的能不能安排
* 不能就下一个
* 为了方便用排序模板封装了一下
**/
#include <iostream>

using namespace std;

template <typename T>
void merge(int lo, int mi, int hi, T* a)
{
T* A = a + lo;
int lb = mi - lo;
T* B = new T[lb];
T* BB = B;
for(int i = 0;i < lb;++ i)
B[i] = A[i];
int lc = hi - mi;
T* C = a + mi;
int cnt = 0;
while(1) {
if ((lb == 0) && (lc == 0)) break;
if (lb == 0) {
A[cnt] = C[0];
++ cnt; ++ C; -- lc;
}
else if (lc == 0) {
A[cnt] = B[0];
++ cnt; ++ B; --lb;
}
else {
if(B[0] < C[0]) {
A[cnt] = B[0];
++ cnt; ++ B; -- lb;
}
else {
A[cnt] = C[0];
++ cnt; ++ C; -- lc;
}
}
}
delete []BB;
}

template <typename T>
void mergeSort(int lo, int hi, T* A)
{
if(hi - lo < 2) return;
int mi = (lo + hi) / 2;
mergeSort(lo, mi, A); mergeSort(mi, hi, A);
merge(lo, mi, hi, A);
}

class node {
public:
int t1, t2;
node():t1(0), t2(0) {}
node(const node &obj):t1(obj.t1), t2(obj.t2) {}
bool operator<(const node &obj) {
return t2 < obj.t2;
}
bool operator>(const node &obj) {
return t2 > obj.t2;
}
bool operator==(const node &obj) {
return t2 == obj.t2;
}
friend istream& operator>>(istream &in, node &obj);
};

istream& operator>>(istream &in, node &obj) {
in >> obj.t1 >> obj.t2;
return in;
}

int n, ans = 1;
node a[100233];

int main() {
cin >> n;
for(int i = 0;i < n;++ i)
cin >> a[i];
mergeSort(0, n, a);
int curt2 = a[0].t2;
for(int i = 0;i < n - 1;++ i) {
if(a[i + 1].t1 >= curt2) {
++ ans;
curt2 = a[i + 1].t2;
}
}
cout << ans << endl;
return 0;
}
``````

## skyzh's solution

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

struct Period {
int start, end;
};

Period D[100000];

bool cmp(const Period& a, const Period& b) {
if (a.end == b.end) return a.start > b.start;
return a.end < b.end;
}

int main() {
int N;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> D[i].start >> D[i].end;
}
int idle = -1;
int p = 0;
sort(D, D + N, cmp);
for (int i = 0; i < N; i++) {
if (idle <= D[i].start) {
++p;
idle = D[i].end;
}
}
cout << p << endl;
return 0;
}
``````

## victrid's solution

``````#include <iostream>
using namespace std;
struct t {
int t1;
int t2;
};
t* MergeSort(t* list, int listSize) {
if (listSize == 1)
return list;
if (listSize == 2) {
if (list[0].t2 > list[1].t2) {
t temp  = list[0];
list[0] = list[1];
list[1] = temp;
return list;
}
return list;
}
t* tmplist = new t[listSize];
t* llst    = MergeSort(list, listSize / 2);
t* rlst    = MergeSort(list + listSize / 2, listSize - listSize / 2);
int lct = 0, rct = 0;
while (lct + rct != listSize) {
if ((llst[lct].t2 <= rlst[rct].t2 && lct < listSize / 2) || rct >= listSize - listSize / 2) {
tmplist[lct + rct] = llst[lct];
lct++;
} else {
tmplist[lct + rct] = rlst[rct];
rct++;
}
}
for (int i = 0; i < listSize; i++) {
list[i] = tmplist[i];
}
return list;
}
inline int maxi(int i1, int i2) {
return i1 > i2 ? i1 : i2;
}
int main() {
int n;
cin >> n;
t *timeset = new t[n], *moveptr = timeset;
for (int i = 0; i < n; i++) {
cin >> timeset[i].t1;
cin >> timeset[i].t2;
}
MergeSort(timeset, n);
int* totalis = new int[timeset[n - 1].t2 + 1];
totalis[0]   = 0;
for (int i = 1; i < timeset[n - 1].t2 + 1; i++) {
while (moveptr->t2 < i) {
moveptr++;
}
totalis[i] = totalis[i - 1];
while (moveptr->t2 == i) {
totalis[i] = maxi(totalis[i], totalis[moveptr->t1] + 1);
moveptr++;
}
}
cout << totalis[timeset[n - 1].t2];
return 0;
}
``````

## yyong119's solution

``````#include <cstdio>
#include <algorithm>
#define MAX_N 100010
using namespace std;
struct Node {
int x, y;
bool operator<(const Node &p) const { return y < p.y; }
} a[MAX_N];
int n, cnt, cur_r;
char ch = getchar(); int res = 0, flag = 1;
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') flag = -1, ch = getchar();
while (ch >= '0' && ch <= '9') res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
// return res * flag;
return res;
}
int main() {