2018년 7월 13일 금요일

탐욕알고리즘 - 2

// 구간 스케줄링 p.59
/**
  n개의 강의가 있다. 각 강의 시간은 si에서 ti까지다.
  가장 많은 강의에 참가하고 싶은 경우, 몇 개의 강의에 참가하는 것이 가능할까?

**/
import java.io.*;
// import java.util.TreeMap;
import java.util.*;

class Main {
  public static void main(String[] args) throws IOException {
    
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    final int MAX_N = 100000;  // 비교 최대값
    int N = 5;
    int[] S = {1,2,4,6,8};
    int[] T = {3,5,7,9,10};
    Map map = new TreeMap<>();

    for(int i = 0; i < N; i++) {
      map.put(T[i], S[i]); // 종료시간순으로 정렬한다.
    }

    int ans = 0;
    int t = 0;
    for (int i = 0; i < N; i++) {
      if (t < map.get(T[i])) {
        ans++;
        t = T[i];
        bw.write("선택한 강의 : " + (i+1) + "\n");
      }
    }

    bw.write("ans : " +  ans + "\n"); // 출력 3 (1, 3, 5 선택)
    bw.close();
    // br.close();
  }
  public static int min(int a, int b) {
    if (a > b) return b;
    else return a;
  }
}

댓글 없음 :

댓글 쓰기