## SGU 133 解题报告

http://acm.sgu.ru/problem.php?contest=0&problem=133

## 133. Border

time limit per test: 0.50 sec.
memory limit per test: 4096 KB

Along the border between states A and B there are N defence outposts. For every outpost k, the interval [Ak,Bk] which is guarded by it is known. Because of financial reasons, the president of country A decided that some of the outposts should be abandoned.In fact, all the redundant outposts will be abandoned. An outpost i is redundant if there exists some outpost j such that Aj < Ai and Bi < Bj. Your task is to find the number of redundant outposts.

### Input

The first line of the input will contain the integer number N (1 <=N <= 16 000). N lines will follow, each of them containing 2 integers:Ak and Bk (0 <= Ak < Bk <= 2 000 000 000), separated by blanks. All the numbers Ak will be different. All the numbers Bk will be different.

### Output

You should print the number of redundant outposts.

### Sample Input

```5 0 10 2 9 3 8 1 15 6 11```

`3`

### CODE

```#include<stdio.h> #include<iostream> #include<algorithm> using namespace std;   struct node { int a,b; }D[16005];   bool cmp(node x,node y) { return x.a<y.a; }   int main() { int n,i; scanf("%d",&n); for(i=0;i<n;++i) scanf("%d%d",&D[i].a,&D[i].b); sort(D,D+n,cmp); int l=D[0].a,r=D[0].b,cnt=0; for(i=1;i<n;++i) { if(D[i].b<=r) ++cnt; else r=D[i].b; } printf("%dn",cnt); return 0; }```
» 本博客采用署名 2.5 中国大陆许可协议进行许可，本文版权归作者所有，欢迎转载，但必须在明显位置给出原文连接。