가장 이른 종료 시간으로 활동 선택하기

시작 시간과 종료 시간이 주어진 여러 행사에서 활동 선택 문제는 서로 겹치지 않도록 참석할 수 있는 행사의 최대 개수를 묻습니다. 📅

한 활동이 다른 활동이 끝나기 전에 시작하면 두 활동은 충돌합니다. 서로 겹치는 두 행사 중에서는 하나만 선택할 수 있습니다.

탐욕적 핵심은 아직 선택할 수 있는 행사 중 가장 일찍 끝나는 행사를 항상 고르는 것입니다. 빨리 끝낼수록 다른 행사를 위한 공간이 가장 많이 남습니다.

먼저 모든 활동을 종료 시간 기준으로 정렬하십시오. 그러면 다음 최선의 선택은 이 순서에서 조건에 맞는 첫 번째 활동이 됩니다.

마지막으로 선택한 활동의 종료 시간을 저장할 변수 하나를 두십시오. 새 행사는 호환되려면 이 값과 같거나 그 이후에 시작해야 합니다.

정렬된 리스트를 한 번 훑으십시오. 행사가 마지막 종료 시각과 같거나 그 이후에 시작하면 선택하고, 마지막 종료 시각을 그 행사의 종료 시각으로 갱신하십시오.

비용은 O(n log n)의 정렬 한 번과 이어지는 단일 선형 순회입니다. 대회의 입력이 매우 커도 충분히 빠릅니다.

가장 먼저 끝나는 행사는 일정을 가장 빨리 비워 주므로 더 나은 계획을 방해할 수 없습니다. 어떤 최적 일정에 이 행사를 넣어도 똑같이 좋은 결과를 유지할 수 있습니다.

가장 이른 시작을 기준으로 고르면 하루 전체를 차지하는 긴 행사를 선택할 수 있습니다. 기간만 보아도 잘못 판단할 수 있으므로 종료 시간을 기준으로 하십시오.

한 행사가 다른 행사가 시작하는 순간에 정확히 끝날 때 충돌로 볼지 결정하십시오. 연속된 행사를 허용하려면 시작 시각이 마지막 종료 시각 이상이 되도록 하십시오.

이 패턴은 방 예약, 방송 시청 또는 작업 실행처럼 다양한 문제에 숨어 있습니다. 이 패턴을 발견하면 가장 이른 종료 규칙을 적용할 수 있습니다.

서로 겹치지 않는 활동을 최대한 많이 선택하고 싶습니다.

활동을 종료 시간 기준으로 정렬한 다음, 마지막으로 선택한 활동이 끝난 뒤 시작하는 활동을 차례로 선택하십시오. 정렬 한 번과 순회 한 번으로 최대 집합을 얻을 수 있습니다. 🚀