[알고리즘] Interval Scheduling Algorithm

목적

- 주어진 시간 간격(인터벌)의 집합에서, 서로 겹치지 않는 최대 수의 인터벌을 선택하는 것

 

cf. 각 인터벌은 시작 시간과 종료 시간으로 정의된다

사용

- 효율적인 자원 배분과 일정 관리에 사용된다.

- 서로 겹치지 않는 최대 수의 활동이나 작업을 스케줄링 하는데 유용하다.

예시

1. 프로세스 및 자원 스케줄링
   • 컴퓨터 시스템의 한정된 자원을 여러 프로세스들 사이에서 효율적을 분배
   • 자원이 충돌 없이 사용되도록 하고 시스템 효율성을 최대화
2. 회의실 또는 강의실 예약 시스템
   • 한정된 공간을 여러 그룹이나 이벤트에 할당할 때
   • 최대한 많은 이벤트를 수용할 수 있도록 
3. 항공편 스케줄링
   • 제한된 게이트와 활주로를 가지고
   • 최대한 많은 항공편을 운영할 수 있도록

 

def interval_scheduling(intervals : list[list[int]]):
    # 인터벌을 종료 시간에 따라 정렬
    intervals.sort(key=lambda x: x[1])
    # 겹치지 않는 간격의 최대 집합
    result = []
    current_end_time = -1
    
    for interval in intervals:
        # 아래 조건을 만족하면, 현재 interval 은 result 에 추가된 최근 인터벌과 겹치지 않는다. 
        if interval[0] >= current_end_time:
            result.append(interval)
            # result 에 새롭게 추가된 interval 의 종료 시간으로 current end time 을 업데이트 한다.
            current_end_time = interval[1]
    
    return result

 

궁금해서 확인해본 내용

시작 시간을 기준으로 잡으면 어떻게 될까?

lambda x: x[0]를 사용하여 인터벌을 정렬한다면, 인터벌들은 각각의 시작 시간(x[0])에 따라 정렬된다. 기존의 lambda x: x[1]는 인터벌을 종료 시간에 따라 정렬하여 겹치지 않는 인터벌을 최대한 많이 선택할 수 있도록 한다. 반면에 시작 시간에 따라 정렬하면 다음과 같은 문제가 발생할 수 있다.

 

1. 최적해 도출 실패: 시작 시간에 따라 인터벌을 정렬하면, 알고리즘은 더 이른 시간에 시작하는 인터벌을 우선적으로 선택한다. 이 방법은 겹치지 않는 인터벌의 최대 수를 찾는 것이 아니라, 단순히 빠른 시작 시간을 가진 인터벌을 선택하는 것이므로 최적의 결과를 보장하지 못할 수 있다.
2. 비효율적인 선택: 시작 시간이 빠른 인터벌이 긴 지속 시간을 가질 수 있다. 이 경우, 긴 인터벌이 선택되어 다른 많은 짧은 인터벌들이 제외될 수 있다. 결과적으로, 선택된 인터벌의 총 수가 감소할 수 있으며, 이는 Interval Scheduling Algorithm의 목적에 부합하지 않는다.

예를 들어, 인터벌이 [(1, 4), (2, 3), (3, 5)]와 같이 주어졌다고 가정해보면,

• 종료 시간에 따라 정렬하면 -  [(2, 3), (3, 5)]
• 시작 시간에 따라 정렬하면 - [(1, 4)]

나머지 두 인터벌은 선택되지 못할 수 있다. 

따라서 서로 겹치지 않는 최대 수의 인터벌을 선택하는 interval scheduling algorithm 의 목표에 위배된다.

 

리트코드

https://leetcode.com/problems/non-overlapping-intervals/

Non-overlapping Intervals - LeetCode

 

주의해야 하는 제약사항

• -5 * 104 <= starti < endi <= 5 * 104

current_end_time 을 -inf 로 설정해야

• [[1,2],[2,3],[3,4],[-100,-2],[5,7]]

종료 시간이 0보다 작은 테스트케이스에서 실패하지 않는다.