20121030_problem3

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <memory.h>

#define SEGMENTS_MAX_NUMBER 200000

struct segment {
    int begin, end;
};

void swap(segment * a, segment * b) {
    segment t = *a;
    *a = *b;
    *b = t;
}

int max(int a, int b) {
    return (a < b ? b : a);
}

void fail() {
    printf("No solution");
    exit(0);
}

int n, curBegin, curEnd, ans, rightBorder, prevBorder, cur;
segment segments[SEGMENTS_MAX_NUMBER];

void sort(int l, int r) {
    int i = l, j = r, mediane = l + rand() % (r - l + 1), beginMediane = segments[mediane].begin, endMediane = segments[mediane].end;
    do {
        while (segments[i].begin < beginMediane || segments[i].begin == beginMediane && segments[i].end < endMediane) ++i;
        while (segments[j].begin > beginMediane || segments[j].begin == beginMediane && segments[j].end > endMediane) --j;
        if (i <= j) {
            swap(segments + i, segments + j);
            ++i;
            --j;
        }
    } while (i <= j);
    if (l < j) sort(l, j);
    if (i < r) sort(i, r);
}

int main() {
    srand(time(NULL));
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &curBegin, &curEnd);
        segments[i].begin = curBegin;
        segments[i].end = curEnd;
    }
    sort(0, n - 1);
    if (segments[0].begin > 0) fail();
    ans = rightBorder = prevBorder = cur = 0;
    while (rightBorder < 1000) {
        while (cur < n && segments[cur].begin <= prevBorder) rightBorder = max(rightBorder, segments[cur++].end);
        if (rightBorder == prevBorder) fail();
        ++ans;
        prevBorder = rightBorder;
    }
    printf("%d", ans);
    return 0;
}