[BOJ] 백준 [9576] 책 나눠주기JAVA

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

9576번: 책 나눠주기

문제

풀이

학생들이 각자 받고싶은 책의 범위들에서 적절하게 분배 해 줘야하는데 만약

1번 학생이 1,2,3 의 책 번호를 골랐고
2번 학생이 2,3 책 번호를 골랐다고 하면

2번 학생은 1번책을 받지 못하기때문에  1번 학생에게 우선 1번책을 주고
그다음 2번학생에게 2번 or 3번의 책을 줘야한다.

다른예시로
1번학생이 1,2의 책 번호를 골랐고
2번학생이 2,3의 책 번호를
3번 학생이 2,3을 골랐다고 가정하자

2,3번 학생이 각각 2,3번의 책을 가져가야 하므로 1번학생은 2번책 번호를 골랐지만 가져가면 안된다.
1번 학생은 1번책 , 2번 학생은 2번책 , 3번 학생은 3번책을 가져가면 된다.

n번 학생이 a~b 범위의 책을 골랐고
n+1번 학생이 c~d 범위의 책을 골랐다고 하면
주어진 범위 중 , 끝이 가장 작은 범위의 책을 우선적으로 처리하는것을 목표로 하면된다.
즉 , a<c<b<d 라고 하면 끝 범위는 b가 더 작기때문에 n번 학생에게 a~b 범위의 책을 하나 주면 된다는 것.

만약 끝 범위가 같다면 .. ?
그럼 당연히 책 번호가 작은 순으로 , 맨 앞의 책을 먼저 주면 된다. ( 책의 번호는 1~N까지 순차적으로 부여됨 )

따라서 주어진 학생들의 책 범위가 끝이 작은순으로 먼저 정렬을하고
만약 끝 범위가 같다면 두번째로 범위의 시작번호가 작은 순으로 처리하면 끝.

 

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        while (tc-->0) {
            int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int N = input[0], M = input[1];
            int[][] arr = new int[M][2];
            for(int i=0;i<M;i++)
                arr[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            Arrays.sort(arr,(o1, o2) -> o1[1]==o2[1] ? o1[0]-o2[0] : o1[1]-o2[1]);
 
            int cnt=0;
            boolean[] visit = new boolean[N + 1];
            for(int i=0;i<M;i++){
                for(int j=arr[i][0];j<=arr[i][1];j++){
                    if(visit[j]) continue;
                    cnt++;
                    visit[j]=true;
                    break;
                }
            }
            System.out.println(cnt);
        }
    }
}