蟻本 P.43 区間スケジューリング問題

→へーこういうやり方すんのや

→まずJavaさんPairが無いのが辛いなぁ...

→Comparatorってどうやって実装するんだっけｳﾜｱｱｱ

→闇コードができた。

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Interval_Scheduling_Problem {
  
  static class Pair {
    public int first;
    public int last;
    public Pair(int n, int k) {
      first = n;
      last = k;
    }
  }
  
  static class TheComparatorPair implements Comparator {
    public int compare(Object a0, Object b0) {
      Pair a = (Pair)a0;
      Pair b = (Pair)b0;
      
      if(a.first < b.first) {
        return -1;
      }
      else if(a.first > b.first) {
        return 1;
      }
      else {
        return 0;
      }
    }
    
  }

  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
    int N = stdIn.nextInt();
    int[] tmp = new int[N];
    int[] tmp2 = new int[N];
    Pair[] st = new Pair[N];
    for(int i = 0; i < N; i++) {
      tmp[i] = stdIn.nextInt();
    }
    for(int i = 0; i < N; i++) {
      tmp2[i] = stdIn.nextInt();
    }
    for(int i = 0; i < N; i++) {
      st[i] = new Pair(tmp2[i],tmp[i]);
    }
    TheComparatorPair p = new TheComparatorPair(); 
    Arrays.sort(st,p);
    
    int t = 0; int m = -1;
    for(int i = 0; i < N; i++) {
      if(st[i].last > m) {
        t++;
        m = st[i].first;
      }
    }
    System.out.println(t);
  }
}