597B.md (1207B)
1 Source: https://codeforces.com/problemset/problem/597/B 2 3 B. Restaurant 4 5 time limit per test 6 7 4 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 A restaurant received *n* orders for the rental. Each rental order reserve the restaurant for a continuous period of time, the *i*-th order is characterized by two time values — the start time *l**i* and the finish time *r**i* (*l**i* ≤ *r**i*). 22 23 Restaurant management can accept and reject orders. What is the maximal number of orders the restaurant can accept? 24 25 No two accepted orders can intersect, i.e. they can't share even a moment of time. If one order ends in the moment other starts, they can't be accepted both. 26 27 Input 28 29 The first line contains integer number *n* (1 ≤ *n* ≤ 5·105) — number of orders. The following *n* lines contain integer values *l**i* and *r**i* each (1 ≤ *l**i* ≤ *r**i* ≤ 109). 30 31 Output 32 33 Print the maximal number of orders that can be accepted. 34 35 Examples 36 37 Input 38 39 ``` 40 2 41 7 11 42 4 7 43 ``` 44 45 Output 46 47 ``` 48 1 49 ``` 50 51 Input 52 53 ``` 54 5 55 1 2 56 2 3 57 3 4 58 4 5 59 5 6 60 ``` 61 62 Output 63 64 ``` 65 3 66 ``` 67 68 Input 69 70 ``` 71 6 72 4 8 73 1 5 74 4 7 75 2 5 76 1 3 77 6 8 78 ``` 79 80 Output 81 82 ``` 83 2 84 ```