How many movies to spoil?
Statement
Goal
On Valentine Day, John's girlfriend gives him a bunch of tickets for distinct movies at different times. His job is to watch whole movies by those tickets alone and then spoils her the story for each movie.You will be given the start (a) and end time (b) of each movie. Output the maximum number of movies he can watch entirely
Note: John can only watch one movie at a time and John have to watch the movie completely for it to count.
Movies can be watched successively, see example below
Ex:
3
3 5
4 9
5 8
The output is 2. Because John can only watch the first movie (from 3 to 5) and the second movie (from 5 to 8)
Tip for algorithm: Sort by ending time
Input
First line: n number of given movies.
Next n lines: the starting time a and the ending time b of a movie.
Next n lines: the starting time a and the ending time b of a movie.
Output
The maximum number of movies John can watch entirely from start to end.
Constraints
1 ≤ n ≤100
1 ≤ a ≤ b ≤ 1000
1 ≤ a ≤ b ≤ 1000
Example
Input
3 3 5 4 9 5 8
Output
2
Game modes
Fastest
Test cases
Test 1 Test
Input
3
3 5
4 9
5 8
Output
2
Test 2 Validator
Input
10
148 219
831 887
555 649
429 501
325 390
839 902
993 1082
80 115
707 722
762 775
Output
9
Test 3 Test
Input
20
1 21
35 119
37 89
40 103
24 42
84 163
87 95
17 60
61 76
30 86
13 73
31 125
20 107
13 46
14 30
69 110
43 113
36 62
87 141
99 101
Output
5
Test 4 Validator
Input
30
6 104
28 43
87 92
19 68
7 69
6 75
77 123
91 108
51 91
29 97
55 104
97 178
82 92
18 95
39 116
56 116
26 94
17 93
95 124
87 149
70 164
90 91
21 39
11 90
21 100
63 91
11 42
32 120
24 47
88 129
Output
3
Test 5 Test
Input
50
47 52
40 53
18 58
4 64
24 58
15 69
4 47
38 66
9 12
22 52
23 36
3 45
42 65
17 44
14 15
47 56
8 41
60 69
25 52
56 69
43 61
22 41
22 23
43 62
43 52
51 53
13 57
8 38
49 63
31 34
42 53
58 63
19 46
48 65
59 67
36 68
28 54
50 64
18 32
8 54
32 40
7 68
7 59
28 55
42 69
19 59
46 68
61 61
29 49
7 36
Output
6
Test 6 Validator
Input
70
40 51
44 47
36 48
6 9
7 26
28 48
5 50
10 67
4 27
12 41
34 50
13 31
51 65
28 49
35 59
46 60
24 31
39 58
36 48
4 63
6 13
11 19
29 53
36 58
56 69
10 15
12 50
38 60
4 16
63 69
47 61
54 66
31 33
22 39
3 5
11 61
20 56
17 27
37 46
56 66
11 49
25 37
10 43
20 56
8 37
29 32
30 64
46 59
47 58
22 34
23 49
26 52
7 49
42 43
36 52
3 52
11 33
9 35
33 35
47 68
24 44
37 51
17 19
11 19
8 68
31 66
11 12
45 49
34 50
24 25
Output
11
Test 7 Test
Input
80
4 53
27 67
9 17
42 54
3 22
10 60
8 41
3 58
22 24
11 64
13 31
29 45
25 67
9 15
40 62
29 63
18 67
30 61
40 65
14 18
31 35
23 28
54 61
21 58
50 67
8 53
37 56
48 57
7 19
19 21
67 69
4 9
21 34
19 60
11 68
31 34
53 62
12 57
10 26
43 54
16 39
29 55
24 43
10 19
35 56
10 59
3 48
32 45
8 55
14 23
6 18
55 56
11 58
10 41
60 66
15 54
16 42
48 65
4 9
30 38
16 32
22 24
10 58
29 53
43 57
58 60
6 62
28 41
29 33
7 7
44 57
28 51
21 51
43 62
28 33
19 35
51 51
27 36
17 25
7 8
Output
11
Test 8 Validator
Input
90
16 22
19 21
48 61
30 35
5 65
35 45
4 22
4 21
18 67
24 44
9 51
29 49
46 50
59 59
25 30
9 28
30 39
25 57
8 13
15 17
41 66
32 46
32 34
25 45
21 69
50 52
47 61
51 56
3 54
17 20
19 59
10 15
28 67
67 68
26 47
29 69
15 32
19 23
9 42
13 67
9 37
8 28
29 59
31 61
10 63
27 34
8 22
4 10
34 39
29 62
25 55
51 51
9 34
46 57
45 57
20 62
34 49
23 51
40 47
44 59
28 66
13 33
25 52
12 19
14 48
3 11
15 59
49 62
15 33
16 48
8 29
23 54
28 38
58 64
30 46
14 36
19 50
65 66
15 42
26 52
19 45
14 62
25 51
22 46
27 55
22 48
22 51
26 54
38 48
15 66
Output
13
Solution language
Solution
Stub generator input