문제링크

https://www.acmicpc.net/problem/9576

구현방법

N권의 책

1 ~ N권까지 번호가 적혀있음.

N은 최대 100

M은 최대 1000

이전 상황이 다음 상황에 영향을 준다.

최대 줄수 있는 권의 개수 구하기.

B를 기준으로 오름차순 정리하고 B가 같다면 a를 기준으로 정리한다.

정렬하는 방식만 알게되면 어렵지않을듯.

a를 기준으로 할 경우 나중에 줄 수있는 책이 겹쳐서 못주는 경우가 발생할 수있다.

알고리즘

• 그리디

CODE

import java.util.*;
import java.io.*;


public class Main {

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

        StringTokenizer st;

        int T =Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        while(T --> 0){
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            Point point[] = new Point[M+1];

            for(int idx=  1; idx <=M;idx++){
                st= new StringTokenizer(br.readLine());

                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());

                point[idx] = new Point(a,b);
            }
            Arrays.sort(point, 1, M + 1);

            int ans = 0;
            boolean [] check = new boolean[N+1];

            for(int idx = 1; idx <=M;idx++){
                int a = point[idx].x;
                int b= point[idx].y;

                for(int j = a; j<=b;j++){
                    if(!check[j]){
                        check[j] = true;
                        ans+=1;
                        break;
                    }
                }
            }
            sb.append(ans + "\n");

        }
        System.out.print(sb);

    }

    static class Point implements Comparable<Point>{
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Point o) {
            if(this.y == o.y){
                if(this.x > o.x){
                    return 1;
                }
                else{
                    return -1;
                }
            }
            if(this.y > o.y){
                return 1;
            }else{
                return -1;
            }
        }
    }
}