99클럽 코테 스터디 19일차 TLI - (그리디)

문제 : https://www.acmicpc.net/problem/1374

🚨오늘의 학습🚨

⭐️Priorty Queue⭐️

우선순위가 낮은 것 부터 오름차순 정렬한다

PriorityQueue<Integer> pq = new PriorityQueue<>();

※ Integer 클래스는 이미 Comparable 인터페이스를 구현하고 있습니다.
따라서 Integer의 compareTo 메서드에 따라 오름차순 정렬됩니다.

🚨더 나아가기🚨

⭐️Comparable 구현⭐️

static class Lecture implements Comparable<Lecture>{
  int no;
  int start;
  int end;
  public Lecture(int no, int start, int end){
    this.no = no;
    this.start = start;
    this.end = end;
  }
  // 정렬의 기준 필드 정의
  @Override
  public int compareTo(Lecture o) {
  // start가 같다면 
  if (this.start == o.start) {
        return Integer.compare(this.end, o.end); // end의 오름차순
    }
    // start가 큰 것 우선
    return Integer.compare(this.start, o.start); // start의 오름차순
}

public static class Node implements Comparable<Node>{
        int index;
        int cost;
        public Node(int start, int cost) {
            this.index = start;
            this.cost = cost;
        }
        // 정렬 기준 필드 정의
        @Override
        public int compareTo (Node node) {
            // cost기준
            return Integer.compare(this.cost, node.cost);
        }
    }

🚨만약 ?!🚨

⭐️compareTo 내림차순 정렬⭐️

@Override
public int compareTo(Node node) {
    // 내림차순 정렬을 위해 비교 순서를 반전
    return Integer.compare(node.cost, this.cost); 
    // b.cost - a.cost
}

🗝️ 강의 시작시간이 빠른것 && 강의 종료시간이 빠른 강의 우선 배정

🗝️ 겹치는 시간대의 강의의 경우 강의실 추가

---

public class BJN_1374 {

    static class Lecture implements Comparable<Lecture>{
        int no;
        int start;
        int end;

        public Lecture(int no, int start, int end){
            this.no = no;
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(Lecture o) {

            if(this.start == o.start)
                return this.end - o.end;
            return this.start - o.start;
        }
    }

    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int cnt = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());

        Lecture[] arr = new Lecture[cnt];

        for(int i=0; i<cnt; i++){
            arr[i] = new Lecture(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
            st = new StringTokenizer(br.readLine());

        }

        Arrays.sort(arr);

        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int i = 0; i < cnt; ++i) {
            if (pq.isEmpty()) {
                pq.add(arr[i].end);
            } else {
                int endTime = pq.peek();
                if (arr[i].start < endTime) {
                    pq.add(arr[i].end);
                } else {
                    pq.poll();
                    pq.add(arr[i].end);
                }
            }
        }

        System.out.println(pq.size());

    }

}