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;
}

댓글을 작성하려면 로그인해야 합니다.