[Kickstart][2020][Round F] 2. Metal Harvest

문제 : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff48/00000000003f4b8b#problem

---

소행성에 로봇을 설치하여 탐사하려고 한다. 한 번에 하나의 로봇만 기동할 수 있으며 여러 로봇을 한 번에 기동할수는 없다.

로봇은 수확할 수 있는 시간과 관계없이 K배수 시간만큼  배치가 가능하며 연속배치만 가능하다. 

i  번째 로봇은 로봇이 가지는 고유 시간범위 [Si, Ei] 동안 수확이 가능하다. 이 기간은 서로 겹치지 않는다.

로봇 수 N, 배치가능 시간 K, 로봇들의 수확가능시간 배열 S, E가 주어질 때, 가능한 계속 수확하기 위해 로봇을 배치하는데 필요한 최소 로봇 배치 개수는 몇개인지 구하라.

---

각 로봇들의 수확 기간이 서로 겹치지 않기 때문에 많이 쉬워졌다.

시작시간을 기준으로 S, E 배열을 오름차순 정렬한다. 만약 시작시간이 같다면 종료시간을 기준으로 오름차순정렬한다.

마지막 로봇이 종료된 시간(let, end)을 저장한다.

정렬된 로봇들의 시간범위를 앞에서부터 탐색하면서 현재 탐색중인 로봇의 시작시간과 end 변수 중 큰 값이 시작시간이 된다.

만약 로복의 수확 종료시간이 시작시간보다 작거나 같다면 수확이 불가능하므로 다음 로봇을 탐색한다.

탐색이 가능하다면 end ~ 수확 종료시간의 범위를 탐색하기 위해 K시간이 몇번 나타나는지 구한다.

나누기를 쓰면 나머지 타임을 포함시킬 수 없으므로 범위(수확종료시간 - end)에 나머지 시간도 구할 수 있게 하기 위해 K - 1 을 더한 후 K를 나눠준다.

계산 후 end 변수를 갱신한다.

현재 탐색중인 로봇의 총 배치 개수는 (수확종료시간 - end + K - 1) / K 이다.

정답은 모든 로봇의 배치 개수의 합이된다.

 

시간복잡도는 정렬하는데 드는 시간인 O(NlogN)

 

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/codejam/kickstart/2020/roundF/2.%20Metal%20Harvest.cpp