알고리즘을 찾는 최대 범위의 겹치지 않는다.(I.e., 가중치 간격을 예약 Prob.)

Question

질문과 매우 비슷하다 알고리즘을 찾아 가장 긴 겹치지 않는 순서.

유일한 차이점을 연결된 질문은 그 대신을 찾는 설정의 겹치지 않는 튜플 나타내 긴 순서, 을 찾을 필요가 세트의 겹치지 않는 튜플 나타내 최대 범위, 을 의미합 sum 튜플의 길이가 최대(a 튜플 길이 인 last - first + 1 어의 정의 tuple 에서의 다음 문장).

나는 나 튜플 보다 다르게 연결된 문제입니다.대 (starting index, length), 는 내 튜플 (first, last);예를 들어,tuple (3,7) 을 나타내는 숫자의 집 [3, 4, 5, 6, 7].(Tuple 겹치 다른 튜플는 경우에도 결국-포인트 경기;즉, (2,6) 고 (6,8) 겹치 수 없습니다 따라서 모두 나타나 솔루션입니다.)

예를 들어,다음 설정의 튜플으로 정렬 first:

[(0,100), (2,50), (30,150), (60,95), (110,190), (120,150), (191,200)]

최대는 여기서 설정한 것 [(0,100), (110,190), (191,200)] 와의 범위 101 + 81 + 10 = 192.(주는 튜플에서 이 솔루션 비 겹치.)

는 무엇입의 예시 적어도 복잡한 알고리즘을 이를 해결하기 위해,그리고 무엇입의 복잡도는 알고리즘?(할 수 있습니다면 이 해결할 수 있에 O(N), 지만,나는 알고 있지 않다면 그 순간에 그것이 될 수 있습니다.)

부록: 에서 생각해 보면,그것은 질문에 나는 여기에 해당하는 가중치 간격 scheduling 문제.이것은 특별한 경우 일정 간격 문제.

@j_random_hacker 의 응답,수수료가 없습니다 사실,알려진 솔루션을 가중치 간격을 예약하는 문제로,복잡도에서의 시간 O(N log(N)).

Answer 1

여기에는 O(nlog n)-시간,O(n)-공간 알고리즘이 있습니다.첫째,정열의 튜플여 자신의 위치를 시작하지 않을 경우 이에 이의 순서.나는 가정로 배열 색인.

Let's 화의 시작 위치 튜플 i b(i)그리고 끝 위치 e(i),그래서는 해당 총 길이는 e(i)-b(i)+1 입니다.또한 하자 정의 기능은 다음을(나)반환하는 위치에 tuple 목록 첫 번째는 튜플 나타날 수 있습하는 오른쪽의 튜플 i.통지는 다음(i)에 계산할 수 있습 O(로그 n)간으로 검색:유지 모든 튜플 시작 위치한 b(i)array b[],그리고 검색에 대한 첫 번째 j 에 배열 b[i+1..n-1]데 b[j]>e(i).

자 정 f(i)하는 최대 범위의 겹치지 않는 튜플의 집에서 시작 또는 후에 튜플 i.부터는 튜플 나는 자신은 하나에서 최적의 설정 또는지,우리는 가지고 있습니다:

f(i) = max(e(i) - b(i) + 1 + f(next(i)), f(i+1)) for 0 <= i < n

우리는 또한 경계 조건 f(n) = 0.

명확하게 가능한 가장 큰 적용 범위에 의해 주어진 f(0)입니다.이것은 쉽게 계산됩니다.에서 의사의 C++:

int b[] = /* Tuple beginning positions, in nondecreasing order */;
int e[] = /* Tuple end positions */;
int n = /* Number of tuples */;

// Find the array position of the leftmost tuple that begins to the right of
// where tuple i ends.
int next(int i) {
    return upper_bound(b + i + 1, b + n, e[i]);
}

int maxCov[n + 1];    // In practice you should dynamically allocate this

// After running this, maxCov[i] will contain the maximum coverage of any
// nonoverlapping subset of the set of n - i tuples whose beginning positions
// are given by b[i .. n-1] and whose ending points are given by e[i .. n-1].
// In particular, maxCov[0] will be the maximum coverage of the entire set.
void calc() {
    maxCov[n] = 0;
    for (int i = n - 1; i >= 0; --i) {
        maxCov[i] = max(e[i] - b[i] + 1 + maxCov[next(i)], maxCov[i + 1]);
    }
}

루프 calc() 실행 n 시간,그리고 각각 반복하게 한 O(로그 n)호출을 검색 기능 upper_bound().

우리는 재구성 할 수 있습니다 실제 세트의 크기를 계산하여 모두 입력 max()f(0),보고는 하나 실제적으로 생성,최대 녹화는지 그것의 의미의 존재 여 tuple0,다음 recursing 을 처리하는 나머지(대응하는 하나 f(다음(0))또는 f(1))입니다.(있다면 두 입력 같은 다음 여러 개 있는 최적의 솔루션과 우리가 할 수 있습 따라 중 하나입니다.)

Answer 2

알고리즘은 아래에 의해 작동을 재귀적으로 검색하는 가장 큰 비 겹치는 설정하는 각 요소는 가장 왼쪽의 구성원이 돌아와서 가장 커버합니다.댓글을 참조 코드입니다.

에서 구현됩니다.테스트할 수 있습니다 그것은 여기에서 http://viper-7.com/xowTRF

이 알고리즘의 복잡성 O(2^N) 나 O(N^2) 캐싱하가 동의하지 않는다.

$set = [[0,100], [2,50], [30,150], [60,95], [110,190], [120,150], [191,200]];
$GLOBALS['cache'] = array(); //cache for overlapping sub problems

function maximumSet($set) {

    if(count($set) === 1) {
        return $set;
    }

    $cache_key = [];

    foreach($set as $k) {
        $cache_key[] = implode($k,'.');
    }

    $cache_key = implode('_',$cache_key);

    if(isset($GLOBALS['cache'][$cache_key])) {
        return $GLOBALS['cache'][$cache_key];
    }

    $maximumResult = null;

    //for each element in the set,
    //get the largest non-overlapping set that the element is a member of
    //once all N sets have been computed, return the largest one
    foreach($set as $k => $element) {

        unset($set[$k]);

        //create a new set $copy, which contains the remaining elements that
        //do not overlap with $element            
        $copy = $set;

        foreach($set as $k2 => $element2) {
            if($element2[0] <= $element[1]) { 
                //element is considered non overlapping if its start 
                //is less than or equal to current element's end
                unset($copy[$k2]);
            }
            else break; //because the list is sorted we can break the 1st time
            //see a non-overlapping element
        }

        if(!empty($copy)) {
            //if there is at least one non-overlapping element
            //recursively get the maximum set
            $maximumSubset = maximumSet($copy);
            //prepend the current element to it
            array_unshift($maximumSubset,$element);
        }
        else {
            //otherwise the maximum non-overlapping set which contains this element
            //is the element itself                
            $maximumSubset = [$element];
        }

        //store the set in the results by coverage
        $coverage = getCoverage($maximumSubset);
        if(is_null($maximumResult) || $maximumResult['coverage'] < $coverage) {
            $maximumResult = [
                'coverage' => $coverage,
                'set' => $maximumSubset
            ];
        }
    }

    $GLOBALS['cache'][$cache_key] = $maximumResult['set'];
    return $maximumResult['set'];
}

function getCoverage($set) {
    $range = 0;
    foreach($set as $v) {
        $range += ($v[1] - $v[0]);
    }
    return $range;
}

$x = maximumSet($set);
print "<pre>";
print_r($x);
print "</pre>";