처음 생각했을때 큐를 사용해서 모든 경우의 수를 탐색하는 방법을 사용했다. 하지만 이는 O(N^2)의 시간복잡도를 가지는데 최대 100000개의 회의가 생길수 있으니 100000^2=10000000000 즉 최악의 경우 100억번의 연산이라는 결과를 맞이하게 된다. 이는 2초안에 풀수 없음을 의미하기 때문에 시간초과라는 글을 본뒤 푸는 방법을 변경했어야 했다.
또 생각든 게 끝나는 시간의로 솔팅을 하게 된다면 해결이 가능하지 않을까였다. 끝나는 시간으로 솔팅을 하게 되면
(1,100), (2,101), (101, 800), (800,3000) , (100,10000)이면 1이 100으로 100이 10000으로 가기 때문에 2번째부터 시작하는게 맞지 않나라는 고민이 들었다. 하지만 이는 의외로 간단하게 풀리는데 첫번째를 고르고 굳이 100이 아니라 100보다 큰 끝나는 시간이 빨리 끝나는 녀석을 고르면 되는 것이다.
또한 구현에서도 prioriy_queue를 선택했는데 이 녀석에 처음 element들을 넣었을때 전부가 정렬이 되지 않아서 적잖게 당황했다. 이유는 priority_queue 자체는 원소가 들어오거나 빠질때 Heap sort algorithm을 수행한다. 그러므로 빼거나 넣는 횟수가 n번이라면 이는 nlogn의 시간복잡도를 가진다. 좀더 정확한 분석은 힙솔트를 공부하고 하겠다.
코드 :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | <code class="hljs cpp"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> </span><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> </span><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> </span><span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> std;<span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">confer_info</span> {</span> <span class="hljs-keyword">int</span> start_time; <span class="hljs-keyword">int</span> end_time; <span class="hljs-built_in">confer_info</span>(<span class="hljs-keyword">int</span> start, <span class="hljs-keyword">int</span> end) : <span class="hljs-built_in">start_time</span>(start),<span class="hljs-built_in">end_time</span>(end){}};<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">cmp</span> {</span><span class="hljs-keyword">public</span> : <span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">operator</span><span class="hljs-params">()</span><span class="hljs-params">(confer_info s1, confer_info s2)</span> </span>{ <span class="hljs-keyword">if</span> (s1.end_time != s2.end_time) <span class="hljs-keyword">return</span> s1.end_time > s2.end_time; <span class="hljs-keyword">else</span> <span class="hljs-keyword">return</span> s1.start_time > s2.start_time; }};<span class="hljs-keyword">int</span> N, ans;<span class="hljs-keyword">int</span> start_time, end_time;priority_queue<confer_info, vector, cmp> pq;<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">Input</span><span class="hljs-params">()</span> </span>{ <span class="hljs-built_in">scanf</span>(<span class="hljs-string">"%d"</span>, &N); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i < N; i++) { <span class="hljs-built_in">scanf</span>(<span class="hljs-string">"%d %d"</span>, &start_time, &end_time); pq.<span class="hljs-built_in">push</span>(confer_info{ start_time, end_time }); }}<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">Calc</span><span class="hljs-params">()</span> </span>{ <span class="hljs-keyword">int</span> max_time = <span class="hljs-number">0</span>; <span class="hljs-keyword">while</span> (!pq.<span class="hljs-built_in">empty</span>()) { <span class="hljs-keyword">int</span> start_time = pq.<span class="hljs-built_in">top</span>().start_time; <span class="hljs-keyword">int</span> end_time = pq.<span class="hljs-built_in">top</span>().end_time; pq.<span class="hljs-built_in">pop</span>(); <span class="hljs-keyword">if</span> (max_time <= start_time) { max_time = end_time; ans++; } } <span class="hljs-built_in">printf</span>(<span class="hljs-string">"%d"</span>, ans);}<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">Solve</span><span class="hljs-params">()</span> </span>{ <span class="hljs-built_in">Input</span>(); <span class="hljs-built_in">Calc</span>();}<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">(<span class="hljs-keyword">void</span>)</span> </span>{ <span class="hljs-built_in">Solve</span>(); <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;}</code> |