Skiena Design on Algorithm

Question

Skiena의 Design on Algorithms에 문제가 있습니다. 내 솔루션이 맞는지 잘 모릅니다.

5-18. 영화 M_1, M_2, .. M_k의 세트를 생각해 보자. 이번 주말에보고 싶어하는 두 개의 영화를 보여주는 고객이 있습니다. 영화는 토요일 저녁과 일요일 저녁에 상영됩니다. 동시에 여러 영화를 상영 할 수 있습니다. 토요일에 어떤 영화를 방영해야하는지, 일요일에는 어떤 영화를보아야하는지 결정해야합니다. 그러면 모든 고객이 원하는 두 개의 영화를 볼 수 있습니다. 각 영화가 한 번만 표시되는 일정이 있습니까? 그러한 스케줄이있을 경우이를 찾기위한 효율적인 알고리즘을 설계하십시오.

솔루션 : 동영상에는 {M1, M2..Mk} 세트가 있고 costumers에는 {C1, C2, .. Cp} 세트가 있습니다. C1에서보고 싶은 C1의 가장자리 2 개와 연결합니다. C2가보고 싶어하는 영화의 가장자리 2 개와 연결하십시오. 영화 세트가 연결된 그래프가됩니다. 같은 밤에 2 개의 좋아하는 영화를 볼 수 없었던 것과 같은 2 부분 그래프인지 확인하고 싶습니다 (색상 2 우리가 토요일과 제 2 색 일요일에 제 1 색으로 착색 한 모든 영화를 보여줍니다. 문제는 해결되었습니다. 그러나 내가 어떻게해야합니까?

Answer 1

우리는 동시에 영화를 볼 수 있다고 언급합니다. 토요일과 일요일 두 세트를 가져 가십시오. 각 고객은 그가보고 싶은 영화가 토요일과 태양에 임의로 배치되지 않고 계속 진행되는 경우 다른 세트에 있는지 확인하십시오. 그들이 동일한 세트에있는 경우, 다른 세트에 그 중 하나를 넣으십시오. 최악의 경우 각 영화는 토요일과 일요일에 모두 공개됩니다.