Algorithm
Polycarpus likes studying at school a lot and he is always diligent about his homework. Polycarpus has never had any problems with natural sciences as his great-great-grandfather was the great physicist Seinstein. On the other hand though, Polycarpus has never had an easy time with history.
Everybody knows that the World history encompasses exactly n events: the i-th event had continued from the year ai to the year bi inclusive (ai < bi). Polycarpus easily learned the dates when each of n events started and ended (Polycarpus inherited excellent memory from his great-great-granddad). But the teacher gave him a more complicated task: Polycaprus should know when all events began and ended and he should also find out for each event whether it includes another event. Polycarpus' teacher thinks that an event j includes an event i if aj < ai and bi < bj. Your task is simpler: find the number of events that are included in some other event.
The first input line contains integer n (1 ≤ n ≤ 105) which represents the number of events. Next n lines contain descriptions of the historical events, one event per line. The i + 1 line contains two integers ai and bi (1 ≤ ai < bi ≤ 109) — the beginning and the end of the i-th event. No two events start or finish in the same year, that is, ai ≠ aj, ai ≠ bj, bi ≠ aj, bi ≠ bj for all i, j (where i ≠ j). Events are given in arbitrary order.
Print the only integer — the answer to the problem.
5
1 10
2 9
3 8
4 7
5 6
4
5
1 100
2 50
51 99
52 98
10 60
4
1
1 1000000000
0
In the first example the fifth event is contained in the fourth. Similarly, the fourth event is contained in the third, the third — in the second and the second — in the first.
In the second example all events except the first one are contained in the first.
In the third example only one event, so the answer is 0.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
int pairCompare(const std::pair<long,long> &lhs, const std::pair<long,long> &rhs){return (lhs.first < rhs.first);}
int main(){
long n(0); scanf("%ld", &n);
std::vector<std::pair<long, long>> events;
long start(0), finish(0);
for(long k = 0; k < n; k++){
scanf("%ld %ld", &start, &finish);
events.push_back(std::pair<long,long>(start,finish));
}
std::sort(events.begin(), events.end(), pairCompare);
long count(0), currentMaxEnd(0);
for(int k = 0; k < n; k++){
if(events[k].second < currentMaxEnd){++count;}
else{currentMaxEnd = events[k].second;}
}
printf("%ld\n", count);
return 0;
}Input
1 10
2 9
3 8
4 7
5 6
Output
Demonstration
Codeforces Solution-C. History-Solution in C, C++, Java, Python