int N; struct smeet { int b, e; }; smeet meet[100001]; smeet mcopy[100001];
int max(int a, int b) { return (a > b) ? a : b; }
void merge(int start, int end) { int mid = (start + end) / 2; int left = start; int right = mid + 1; int ck = left; while (left <= mid && right <= end) { if (meet[left].e <= meet[right].e) mcopy[ck++] = meet[left++]; else mcopy[ck++] = meet[right++]; }
while (left <= mid) mcopy[ck++] = meet[left++];
while (right <= end) mcopy[ck++] = meet[right++];
for (int i = start; i <= end; ++i) { meet[i] = mcopy[i]; } }
void sort(int start, int end) { if (start == end) return;
int mid = (start + end) / 2;
sort(start, mid); sort(mid + 1, end);
merge(start, end); }
int f() { int beg, selected, end; beg = 0; selected = 0; end = 0; for (int i = 0; i < N; ++i) { beg = meet[i].b; if (meet[i].b > meet[i].e) continue;
if (meet[i].b == meet[i].e || end <= beg) { end = meet[i].e; selected++; } }
return selected; } int main() { cin >> N;
for (int i = 0; i < N; ++i) { cin >> meet[i].b >> meet[i].e; }
intotime 8년 전
#include <iostream>
using namespace std;
int N;
struct smeet
{
int b, e;
};
smeet meet[100001];
smeet mcopy[100001];
int max(int a, int b)
{
return (a > b) ? a : b;
}
void merge(int start, int end)
{
int mid = (start + end) / 2;
int left = start;
int right = mid + 1;
int ck = left;
while (left <= mid && right <= end)
{
if (meet[left].e <= meet[right].e)
mcopy[ck++] = meet[left++];
else
mcopy[ck++] = meet[right++];
}
while (left <= mid)
mcopy[ck++] = meet[left++];
while (right <= end)
mcopy[ck++] = meet[right++];
for (int i = start; i <= end; ++i)
{
meet[i] = mcopy[i];
}
}
void sort(int start, int end)
{
if (start == end) return;
int mid = (start + end) / 2;
sort(start, mid);
sort(mid + 1, end);
merge(start, end);
}
int f()
{
int beg, selected, end;
beg = 0;
selected = 0;
end = 0;
for (int i = 0; i < N; ++i)
{
beg = meet[i].b;
if (meet[i].b > meet[i].e) continue;
if (meet[i].b == meet[i].e || end <= beg)
{
end = meet[i].e;
selected++;
}
}
return selected;
}
int main()
{
cin >> N;
for (int i = 0; i < N; ++i)
{
cin >> meet[i].b >> meet[i].e;
}
sort(0, N - 1);
cout << f() << "\n";
return 0;
}