/*
有n项工作,每项工作分别在si时间开始,在ti时间结束.
对于每项工作,你都可以选择参与与否.如果选择了参与,那么自始至终都必须全程参与.
此外,参与工作的时间段不能重复(即使是开始的瞬间和结束的瞬间的重叠也是不允许的).
你的目标是参与尽可能多的工作,那么最多能参与多少项工作呢?

1≤n≤100000
1≤si≤ti≤10^9

输入:
第一行:n
第二行:n个整数空格隔开,代表n个工作的开始时间
第三行:n个整数空格隔开,代表n个工作的结束时间

样例输入:
5
1 3 1 6 8
3 5 2 9 10

样例输出:
3

说明:选取工作1,3,5
 */

 

思路：
找结束时间最短的任务

 1 import java.util.Arrays;
 2 import java.util.Scanner;
 3 
 4 public class test46 {
 5     private static class Job implements Comparable<Job>{
 6 
 7         int s;
 8         int t;
 9         
10         public Job(int s, int t) {
11             this.s = s;
12             this.t = t;
13         }
14 
15         @Override
16         public int compareTo(Job other) {
17             int x = this.t-other.t;
18             if(x == 0){
19                 return this.s-other.s;
20             }else{
21                 return x;
22             }
23         }
24     }
25     
26     private static int f(int n, Job[] jobs){
27         int cnt = 1;
28         int y = jobs[0].t;
29         for(int i = 0; i < n; i++){
30             if(jobs[i].s > y){
31                 cnt++;
32                 y = jobs[i].t;
33             }
34         }
35         return cnt;
36     }
37     
38     public static void main(String[] args) {
39         Scanner in = new Scanner(System.in);
40         int n = in.nextInt();
41         int[] s = new int[n];
42         int[] t = new int[n];
43         Job[] jobs = new Job[n];
44         
45         for(int i = 0; i < n; i++){
46             s[i] = in.nextInt();
47         }
48         for(int i = 0; i < n; i++){
49             t[i] = in.nextInt();
50         }
51         for(int i = 0; i < n; i++){
52             jobs[i] = new Job(s[i], t[i]);
53         }
54         
55         Arrays.sort(jobs);
56         int res = f(n, jobs);
57         System.out.println(res);
58     }
59 }