인터벌 스케줄링
인터벌 스케줄링이란
인터벌 스케줄링이란
인터벌 스케줄링은 주어진 작업을 최대한 많이 수행할 수 있도록 겹치지 않는 작업의 최대 집합을 찾거나,
혹은 최대한 적은 개수의 리소스를 사용하여 겹치는 작업을 처리하는 문제이다.
인터벌 스케줄링의 조건
- 각 작업은 고유한 시작 시간과 종류 시간이 존재한다.
- 작업 j는 구간 [S_j,F_j]로 표현되며, 시작 시간 S_j와 종료시간 F_j가 주어진다. - 겹치는 작업은 동시에 수행할 수 없다.
- 정렬 기준이 중요하다.
- 최대 작업 선택 문제 : 예시) 회의실배정
종료 시간이 빠른 순으로 정렬 => 가장 많은 작업을 배정할 수 있다.- 최소 작업 선택 문제 : 예시) 단속 카메라 배치
종료 시간이 빠른 순으로 정렬 => 최소한의 자원으로 모든 작업을 커버할 수 있다.
- 최소 작업 선택 문제 : 예시) 단속 카메라 배치
참고 : https://en.wikipedia.org/wiki/Interval_scheduling
예시
최솟 값 찾기
https://school.programmers.co.kr/learn/courses/30/lessons/42884
문제 핵심
- 차량의 이동 경로가 겹치지 않도록 최소한의 카메라를 배치해야 함.
- 최소한의 포인트로 모든 간격을 커버하는 문제.
풀이
- 종료 지점을 기준으로 정렬 -> 가장 빨리 끝나는 구간부터 처리
- 각 경로를 순회하면서 현재 카메라로 감시되지 않는 차량이 나오면 새로운 카메라 배치
- 카메라 위치를 마지막으로 설치한 종료 지점으로 업데이트
코드
// 종료 지점을 기준으로 정렬
// 가장 빨리 끝나는 구간부터 처리
bool comp(vector<int>& a, vector<int>& b)
{
return a[1] < b[1];
}
int solution(vector<vector<int>> routes)
{
int answer = 0;
// 종료 지점을 기준으로 정렬
sort(routes.begin(), routes.end(), comp);
int pos = -30001;
// 각 경로를 순회
for(const auto& route : routes)
{
int begin = route[0];
int end = route[1];
// 현재 카메라로 감시되지 않는 차량이 나오면
if(pos < begin)
{
// 새로운 카메라 배치
answer++;
// 카메라 위치를 마지막으로 설치한 종료 지점으로 업데이트
pos = end;
}
}
return answer;
}최댓 값 찾기
https://www.acmicpc.net/problem/1931
문제 핵심
- 가능한 최대 개수의 회의를 배정해야 함.
- 서로 겹치지 않는 최대한 많은 회의를 선택하는 문제.
풀이
- 회의 종료 시간을 기준으로 정렬 → 빨리 끝나는 회의를 먼저 선택.
- 회의가 끝나는 시간이 같을 때 고려 - 각 회의를 순회하면서 현재 회의가 마지막 선택된 회의와 겹치지 않으면 새로운 회의 선택.
- 마지막 회의 종료 시간을 업데이트.
코드
// 회의 종료 시간을 기준으로 정렬
// 빨리 끝나는 회의를 먼저 선택하도록 한다.
bool comp(vector<int> &a, vector<int>& b)
{
if(a[1] == b[1])
{
return a[0] < b[0];
}
return a[1] < b[1];
}
int main()
{
int answer = 0;
int N;
cin >> N;
vector<vector<int>> meetings(N, vector<int>(2, 0));
for(int i=0; i<N; ++i)
{
cin >> meetings[i][0] >> meetings[i][1];
}
// 회의 종료 시간을 기준으로 정렬한다.
sort(meetings.begin(), meetings.end(), comp);
int endsTime = -1;
for(const auto& meeting : meetings)
{
// 현재 회의가 마지막 선택된 회의와 겹치지 않으면
if(meeting[0] >= endsTime)
{
// 새로운 회의 선택
++answer;
// 회의가 끝나는 시간 업데이트
endsTime = meeting[1];
}
}
cout << answer;
return 0;
}
Hello World