weighted interval scheduling

어떤 테스크가 N개 주어진다. 각 테스크는 시작시간, 종료시간, 가중치를 가지고 있다.
같은 시간에 2개 이상의 테스크를 처리할 수 없을 때 최대로 얻을 수 있는 가중치의 합을 구하라

(2차원이지만 접근법이 비슷하다고 생각함)

방법:
간단히 dp로 n^2에 풀 수 있지만 nlgn으로 줄일 수 있다. 
테스크들의 시작점과 끝점을 분리하고 인덱스를 같이 저장하여 시간 순으로정렬한다. (이때 시작점인지 끝점인지 알 수 있도록 한다.) 정렬한 데이터를 선형으로 보면서 시작점일 경우 이전에 구한 최대값과 같이 계산해서 저장해 놓는다.(최대값을 바로 갱신하지 않는다.) 끝점일 경우 최대값을 갱신한다. (binary search로 현재 보는 테스크와 겹치지 않고 인덱스가 가장 큰 테스크를 찾아도 될것 같다.)


댓글

댓글 쓰기

이 블로그의 인기 게시물

BOJ 11478 - 서로 다른 부분 문자열의 개수

길이 $N$인 문자열 $S$의 서로 다른 부분 문자열의 개수를 세는 문제이다. 방법 1) Suffix Array + LCP $O(NlgN)$에 해결할 수 있다. 다른 곳에서 많이 볼 수 있는 풀이이다. 방법 2) 트라이 $O(N^2)$에 해결할 수 있다. 트라이에 $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 모두 넣으면 최종적으로 트라이에 존재하는 노드의 수 - 1(루트 제외)이 답이 된다. 방법 3) 해싱 $O(N^2lgN)$에 해결할 수 있다. $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 해싱하면서 유니크한 해싱값들의 수를 세면 된다. 코드 (트라이) :  http://ideone.com/bugbDy 코드 (해싱) :  http://ideone.com/hkjw5n
계속 읽기

repeated squaring

https://www.acmicpc.net/problem/1533 최대 가중치 5인데 한 정점을 정점 다섯개로 치환하고 모든 간선의 가중치가 1인것처럼 만든다. 그런식으로 만든 인접행렬을 거듭제곱하면 답을 구할 수 있다. http://codeforces.com/problemset/problem/621/E
계속 읽기