작은 일정 문제에 대한 수학적 솔루션 찾기

Question

용량이있는 회의실 목록과 참석자 수를 가진 회의 목록이 있다고 가정 해보십시오. 각 회의를 다음과 같은 방법으로 하나의 회의실과 일치 시키려합니다.

참석자 수 이상의 회의실에서만 회의를 예약 할 수 있습니다.
1. 잉여 객실이있는 경우 가능한 가장 큰 공간이 예약되지 않도록 회의를 예약해야합니다.
2. 출석이 큰 회의는 출석이 적은 회의보다 작은 회의실에 예약해서는 안됩니다.
3. 주어진 방에서 주어진 회의를 예약하는 것이 불가능한 지 분명히 알아야합니다.

일정에 효율적으로 도착할 수 있습니까? 하나의 패스가 좋을 것입니다. 일부 되돌림은 괜찮지 만, 내가 일할 수있는 유일한 옵션 (거친 알고리즘과 규칙 3의 위반을 동적으로 제거하는 것)은 내가 원하는 것보다 느립니다.

이 질문은 보이는 것처럼 쉽지 않습니다! 우리는 내림차순 각 목록을 정렬하고 가장 큰 세션에 가장 큰 방을 페어링 시작할 수 있습니다

1. , 우리는 솔루션은 어떤 시간을 올 것이다 : 순진 선형 방법은 적어도 하나의 기준은 실패 가능하지만 우리는 가장 큰 것보다는 남은 가능한 가장 작은 방을 가질 것입니다. (200 명, 30 명, 20 명 수용 인원으로 구성된 10 명 및 15 명 회의의 경우를 고려하십시오.)

2. 회의 목록을 고저원으로 정렬 한 다음 아래로 내려서 이 회의를 수용하기에 충분한 크기의 가장 작은 방을 찾으십시오. 그러나 때로는 더 작은 회의를 위해 더 큰 회의실이 예정되기도합니다. (40 인실 및 80 인실의 40 인 및 30 인 회의 계획을 고려해보십시오.)

그러나이 비교적 간단한 문제를 해결하는 더 좋은 방법이 있습니다.

Answer 1

목록을 낮은 값에서 높음으로 정렬 한 다음 각 회의를 보유 할 수있을만큼 큰 첫 번째 (즉 가장 작은) 회의실에 넣을 수는 없습니까?

가 최대한 멀리 볼 수있는 그 모든 기준을 충족 : 우리가 분류 한 이후 이것은 우리가 항상

가능한 가장 작은 방을 선택했다는 사실에서 직접 수행해야

1. 확인을 낮은 출석에서 높은 출석에 회의, 우리는 더 작은 방에있는 더 큰 회의를 결코 두지 않을 것이다.
2. 회의 목록 끝에 도달하기 전에 회의실 목록 끝에 도달하면 일정을 찾을 수 없습니다. 귀하의 코멘트에 응답

편집 :

우리는 두 개의 패스를합니다. 첫 번째는 위를 향합니다. 그 후에 회의가 남아 있으면 다음과 같이 진행하십시오.

객실 목록과 예정되지 않은 회의 목록을 가장 높은 순서에서 가장 낮은 순서로 이동하십시오.

현재 회의가 현재 회의실에 적합한 경우 회의실에 이전 회의실의 회의록을 정렬 순서가 유지되도록 가장 낮은 위치에 추가합니다. 목록의 다음 회의 및 회의실로 이동하십시오.

현재 회의가 현재 회의실에 적합하지 않은 경우 :이 회의는 예약 할 수 없습니다. 목록에서 회의를 제거하고 같은 회의실에서 다음 회의를 시도하십시오.

예약되지 않은 모임 목록이 비어 나올 때까지 반복하십시오.