문제
한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들 려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하 면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중 단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.
[입력설명]
첫째 줄에 회의의 수 n(1<=n<=100,000)이 주어진다. 둘째 줄부터 n+1 줄까지 각 회의의 정 보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 회의의 시작시간과 끝나는 시간의 조건은 (시작시간 <= 끝나는 시간)입니다.
[출력설명]
첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.
입력예제 1
5
1 4
2 3
3 5
4 6
5 7
출력예제 1
3
예제설명
(2, 3), (3, 5), (5, 7)이 회의실을 이용할 수 있다.
입력예제 2
3
3 3
1 3
2 3
출력예제 2
2
문제 풀이
코드
- 그리디 설명 페이지에서 첫번째, 활동 선택 문제의 경우이다. 이 경우 그리디 알고리즘으로 풀면 효과적이다.
직관적으로 생각해봤을 때 최대 사용할 수 있는 회의수를 구하기 위해서는, 최대한 빨리 끝나는 회의를 찾으면 된다. 그럼 그 뒤에 더 많은 회의가 가능하기 때문이다. - 또한, 입력예제 2번째 케이스를 반드시 고려해야한다. 끝나는 시간이 같을 때는, 시작시간으로 오름차순 정렬한다. 이 경우를 고려하지 않으면 100점은 bye...
시작시간>=끝난시간을 만족해야한다. 끝이나야 시작을 할 수 있기 때문이다.
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(meeting){
let answer=0;
//끝시간 같을 때, 시작시간으로 정렬해줄 것(없으면 100점 solve 아님)
meeting.sort((a, b)=>{
if(a[1]===b[1]) return a[0]-b[0]; //끝시간이 같으면 시작시간 기준으로 오름차순 정렬
else return a[1]-b[1]; //끝시간으로 오름차순 정렬
})
let et=0; //end_time
for(let x of meeting){
if(x[0]>=et){
answer++;
et=x[1];
}
}
return answer;
}
//let arr=[[1, 4], [2, 3], [3, 5], [4, 6], [5, 7]];
let arr=[[3, 3], [1, 3], [2, 3]];
console.log(solution(arr));
</script>
</body>
</html>참고
그리디: https://www.zerocho.com/category/Algorithm/post/584ba5c9580277001862f188
내가 짱이다 😎 매일 조금씩 성장하기🌱
2개의 댓글
2021년 9월 15일
9/15
function solution(arr){
let answer=1;
arr.sort((a, b)=>{
if(a[1]===b[1]) return a[0]-b[0];
else return a[1]-b[1];
}); //빨리 끝나는 순서대로
let et=arr[0][1]; //초기값
for(let i=1; i<arr.length; i++){
if(arr[i][0]>=et) {
answer++;
et=arr[i][1];
}
}
return answer;
}
```답글 달기
9/14
1. 직관적으로 생각해봤을 때 최대 사용할 수 있는 회의수를 구하기 위해서는, 최대한 빨리 끝나는 회의를 찾으면 된다.➡️ 끝나는 시간 순서대로 오름차순 정렬하기
2. sort안에 반드시 return