[Codejam][2020][QR] 3. Parenting Partnering Returns

문제 : https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/000000000020bdf9

---

각 활동의 시작, 종료 시간이 주어지면 Jamie, Cameron이 활동을 나눠서 한다고 하자.

활동 중 다른 활동을 중복으로 수행은 불가능하다. (한 번에 하나의 활동만 가능)

두 사람이 모든 활동을 나눠가질 수 없을 때는 IMPOSSIBLE을 출력하자.

가능하다면 각 활동을 수행하는 사람의 이니셜 배열을 구하자.

---

greedy의 대표 문제.

각 활동들의 시작 시간을 기준으로 오름차순 정렬한다. 정렬하면 활동들의 순서가 뒤섞이므로 배열에 인덱스를 추가하고 정렬한다.

Jamie, Cameron 를 순서대로 활동 중인지 체크한다.

이를 위해 활동을 시작할 때 활동의 종료시간을 각자 저장해둔다.

각자의 종료시간보다 현재 탐색중인 활동의 시작시간이 같거나 크다면 활동을 할 수 있다는 뜻이다.

만약 어떤 활동에 대해 두 명다 해당 활동을 할 수 없다면 불가능한 경우이다.

 

시간복잡도는 정렬하는데 드는 시간인 O(NlogN). N = 활동의 개수.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/codejam/2020/QR/3.%20Parenting%20Partnering%20Returns.cpp