leecode 253. Meeting Rooms II

문제 요약

입력값으로 (미팅 시작, 끝)이 주어지고 미팅을 잡을 때 사용할 수 있는 최소한의 회의실 개수를 구하는 문제였습니다.

해결

이 문제의 핵심은 회의 시작 순서로 정렬 후 회의실을 새로 잡을지, 아니면 기존 확보한 회의실을 사용할 수 있는지였습니다. 그것에 대한 판단은  PriorityQueue를 사용하여 찾아낼 수 있었습니다.

만약 (0, 30), (5, 10), (15, 20)이 주어져있다고 생각해봅니다.

만약 queue에 넣은 값 중 최소값이 현재 미팅의 시작 시간보다 크다면 새로운 회의실을 잡아야겠죠. 그렇지 않다면 기존 회의실을 쓰고 새로운 미팅의 끝 시작을 다시 queue에 넣어주면 됩니다(물론 기존 끝시간은 queue에서 빼구요)

교훈

우선 이런 문제는 기준점이 먼저 필요합니다. 그렇기 때문에 시작 시간으로 정렬을 합니다.

 가장 가까운 미팅은 뭐야?

위 질문이 중요합니다. 이것에 따라서 사실 PriorityQueue를 써도 되지만, TreeSet을 통해서 찾아낼 수도 있습니다. 이런 핵심 질문을 떠올리는게 중요한데 이것은 훈련이 되어야겠죠. 하지만 문제의 본질에 초점을 맞추고 생각을 하다보면 어느순간엔 도달할 수 있을거라 생각합니다.