Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- 객체지향
- etf
- 미국주식
- 잉여현금흐름
- StringBuffer
- 다형성
- 백준
- FCF
- 배당성장
- 금리인하
- 자바
- 프로그래머스
- S&P500
- 무디스
- 제태크
- Java
- 인플레이션
- 기업분석
- 알고리즘
- mco
- 오버라이딩
- 주린이
- 금리인상
- 그리디 알고리즘
- object
- XLF
- javascript
- 주식
- 현금흐름표
- 접근제어자
Archives
- Today
- Total
오늘의하루
[Greedy Algorithm] 백준 1931번 : 회의실 배정 (Java) 본문
https://www.acmicpc.net/problem/1931
문제
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.
ㅁ
Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
int result = 0;
StringTokenizer st = null;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[][] meeting = new int[N][2]; // 1 4, 3 5 이런식으로 들어오기 때문이다.
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
meeting[i][0] = Integer.parseInt(st.nextToken());
meeting[i][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(meeting, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if(o1[1] == o2[1]) {
return o1[0] - o2[0];
}else {
return o1[1] - o2[1];
}
}
});
int now = 0;
for (int[] i : meeting) {
//for(int i = 0; i < N; i++){
if(now <= i[0]) {
now = i[1];
result++;
}
}
System.out.println(result);
}
}
Explanation
Comparator 인터페이스를 사용하여 compare 메소드를 구현함으로써 정렬방법을 원하는 방법으로 변경하였습니다.
Result
'Algorithm' 카테고리의 다른 글
[Greedy Algorithm] 백준 5585번 : 거스름돈 (Java) (0) | 2023.08.04 |
---|---|
[Greedy Algorithm] 백준 1541번 : 잃어버린 괄호 (Java) (0) | 2023.08.04 |
[Greedy Algorithm] 백준 11047번 : 동전 0(Java) (0) | 2023.08.04 |
[Greedy Algorithm] 백준 11399번 : ATM(Java) (0) | 2023.08.04 |
[Greedy Algorithm] 백준 2839번 : 설탕 배달 (Java) (0) | 2023.08.04 |
Comments