範囲Sと重複範囲Rのセットが与えられた場合、S内の最小のサブセットを見つけて、encompases R

Question

次は、誰かによって私に与えられた練習の面接の質問です。範囲のセットを考えると

：これまでで
（例えばS = {(1, 4), (30, 40), (20, 91) ,(8, 10), (6, 7), (3, 9), (9, 12), (11, 14)}と対象範囲R（例えばR = (3, 13)与えられた - 3から13に行くの範囲を意味する）にアルゴリズムを書きます。目標範囲をカバーする最小の範囲の範囲を見つけます。範囲内のすべての範囲は、スパニングとみなすために重複する必要がありますターゲット範囲全体。 （この例では、答えは{(3, 9), (9, 12), (11, 14)}だろう。

私は、これは貪欲なアルゴリズムを使用して行われるだろうと考えたのですか？この問題を解決する最良の方法は何ですか。上の例では、我々はすべてのためになります3と交差する数字のうち最大のものを選んでください。次に、私たちが選んだものと同じことをします。（3、9）を選んだので、今度は（9,12）を選びました。同じことをして、次の範囲が12と交差することが分かりました最大値は（11,14）です。

その反復の後、私たちは14が13よりも大きい（私たちの範囲の最大値）ので、私たちは止めることができます。

私はこのアルゴリズムで問題を抱えています、どのように効率的に交差する範囲を照会するのですか？線形探索を試みると、アルゴリズムはO(n^2)になります。私の次の考えは、ループを通過するたびに私たちのリストから交差する範囲のいずれかを横切ることでした。したがって、最初の反復では、（1,4）と（3,9）が交差します。次の反復では、（9,12）,（3,9）および（8,10）のクロスを繰り返します。だから、最後の反復によって、私たちが見なければならないのは、{（30,40）、（20,91）、（6,7）}です。最小> 13、最大で<のすべてをクロスすることで、これをさらに効率的にすることができます3.問題はまだ十分ではないかもしれないということです。私たちの範囲の境界内に重複したシーケンスがたくさんあるという潜在的な問題がまだあります。 {（6,7）、（6,7）、（6,7）、（6,7）、（6,7）}のような範囲のリストには、たとえそれらが私たちにとって役に立たなくても。一意の値を格納するだけであっても（集合内にすべてを入れることによって）、実際に大きな範囲を持つことができます。範囲の範囲はターゲット範囲内ですが、範囲内には範囲が1つありますターゲット範囲全体。

私たちの範囲を照会する効率的な方法は何でしょうか？あるいは、おそらく、この問題を解決するより効率的なアルゴリズムは何でしょうか？

Answer 1

クエリにインターバルツリーを使用することはどうですか？ （https://en.m.wikipedia.org/wiki/Interval_tree）ここで貪欲が働くかどうかは分かりません。我々はRで高いポイントと重複し、選択肢の最後のセットを見れば、それらのそれぞれのために、以前の選択肢の間の重複の可能性は、たとえば、あります。その場合は

R = (2,10) and we have (8,10) and (7,10) both overlapping with (6,8) 

、我々だけ必要パスの2番目の脚として(6,8)の1つの値を格納する。 の低い点に向かってより長い経路を作っているので、(6,8)をもう一度訪れても、より少ない足の数で(6,8)が訪問されたことが既に分かっているので、余分なものになります。したがって、私たちが行っている間隔をなくすあなたの考えは理にかなっています。この作品のようなものはありますか？

leg = 1 
start with the possible end (or beginning) intervals 
label these intervals with leg 
until end of path is reached: 
    remove the intervals labeled leg from the tree 
    for each of those intervals labeled leg: 
    list overlapping intervals in the chosen direction 
    leg = leg + 1 
    label the listed overlapping intervals with leg 

Answer 2

インターバルツリーを使用せずに複雑度O(n log n)の次のアルゴリズムを提案できます。

いくつかの表記を導入しましょう。範囲(X,Y)を範囲(x_i,y_i)でカバーする必要があります。

最初のソート間隔は開始点で(x_i,y_i)です。それはy_iの最大とx_i <= X間隔(x_k,y_k)との間隔(x_i,y_i)から選択でき

O(n log n)がかかります。区間はすでに開始点でソートされているため、区間は条件を満たしながらインデックスを増分することができます。 y_kがX未満の場合、所定のセットと範囲の解はありません。他の場合、区間(x_k,y_k)は 'X'を含み、区間の中で最大終点がXを含む。

ここでは、重複条件を満たすために、間隔(y_k, Y)をカバーする必要があります。 Xを含むすべての区間は終点がy_k+1よりも小さいので、前のステップの最後の区間から開始することができます。

各区間はこの段階で1回だけ使用されたので、この部分の時間複雑度はO(n)であり、合計ではO(n log n)です。解決のための

次のコードスニペットは：

intervals // given intervals from set S 
(X, Y) // range to cover 
sort intervals 
i = 0 // start index 
start = X // start point 
result_set // set to store result 
while start <= Y && i < len(intervals): 
    next_start = intervals[i].y 
    to_add = intervals[i] 
    while intervals[i].x <= start && i < len(intervals): 
     if next_start > intervals[i].y: 
      next_start = intervals[i].y 
      to_add = intervals[i] 
     i++ 
    if(next_start < start): 
     print 'No solution' 
     exit 
    start = next_start 
    result_set add to_add 

Answer 3

あなたの割り当ては、私に興味をそそられたので、私は目標範囲の左側に重なった範囲を反復処理することによって、問題を解決してC++プログラムを書いて、再帰的に検索します目標範囲の残りの部分（右側）をカバーする最小の数の範囲である。

このアルゴリズム（このプログラムには示されていません）に対する重要な最適化は、再帰レベルごとに、ターゲット範囲の左側と重複する範囲を最大量だけ使用し、より少ない量だけ左側に重なる。このルールを採用することで、再帰呼び出しツリーに最大で1つの降下があると考えられます。そのような最適化は、複雑度O（n log（n））を有するアルゴリズムを生成する。 （nは再帰の深さを表し、log（n）は二分探索を考慮して最も重複する範囲を見つける。）

このプログラムは、出力として以下を生成します。ここでは

{ (3, 9) (9, 12) (11, 14) } 

はプログラムです：

#include <utility> // for std::pair 
#include <vector> // for std::vector 
#include <iostream> // for std::cout & std::endl 

typedef std::pair<int, int> range; 
typedef std::vector<range> rangelist; 

// function declarations 
rangelist findRanges (range targetRange, rangelist candidateRanges); 
void print (rangelist list); 


int main() 
{ 
    range target_range = { 3, 13 }; 

    rangelist candidate_ranges = 
     { { 1, 4 }, { 30, 40 }, { 20, 91 }, { 8, 10 }, { 6, 7 }, { 3, 9 }, { 9, 12 }, { 11, 14 } }; 

    rangelist result = findRanges (target_range, candidate_ranges); 

    print (result); 
    return 0; 
} 


// Recursive function that returns the smallest subset of candidateRanges that 
// covers the given targetRange. 
// If there is no subset that covers the targetRange, then this function 
// returns an empty rangelist. 
// 
rangelist findRanges (range targetRange, rangelist candidateRanges) 
{ 
    rangelist::iterator it; 
    rangelist smallest_list_so_far; 

    for (it = candidateRanges.begin(); it != candidateRanges.end(); ++it) { 

     // if this candidate range overlaps the beginning of the target range 
     if (it->first <= targetRange.first && it->second >= targetRange.first) { 

      // if this candidate range also overlaps the end of the target range 
      if (it->second >= targetRange.second) { 

       // done with this level - return a list of ranges consisting only of 
       // this single candidate range 
       return { *it }; 
      } 
      else { 
       // prepare new version of targetRange that excludes the subrange 
       // overlapped by the present range 
       range newTargetRange = { it->second + 1, targetRange.second }; 

       // prepare new version of candidateRanges that excludes the present range 
       // from the list of ranges 
       rangelist newCandidateRanges; 
       rangelist::iterator it2; 
       // copy all ranges up to but not including the present range 
       for (it2 = candidateRanges.begin(); it2 != it; ++it2) { 
        newCandidateRanges.push_back (*it2); 
       } 
       // skip the present range 
       it2++; 
       // copy the remainder of ranges in the list 
       for (; it2 != candidateRanges.end(); ++it2) { 
         newCandidateRanges.push_back (*it2); 
       } 

       // recursive call to find the smallest list of ranges that cover the remainder 
       // of the target range not covered by the present range 
       rangelist subList = findRanges (newTargetRange, newCandidateRanges); 

       if (subList.size() == 0) { 
        // no solution includes the present range 
        continue; 
       } 
       else if (smallest_list_so_far.size() == 0 ||    // - first subList that covers the remainder of the target range 
         subList.size() < smallest_list_so_far.size()) // - this subList is smaller than all previous ones checked 
       { 
        // add the present range to the subList, which represents a solution 
        // (though possibly not optimal yet) at the present level of recursion 
        subList.push_back (*it); 
        smallest_list_so_far = subList; 
       } 
      } 
     } 
    } 
    return smallest_list_so_far; 
} 

// print list of ranges 
void print (rangelist list) 
{ 
    rangelist::reverse_iterator rit; 
    std::cout << "{ "; 
    for (rit = list.rbegin(); rit != list.rend(); ++rit) { 
     std::cout << "(" << rit->first << ", " << rit->second << ") "; 
    } 
    std::cout << "}" << std::endl; 
} 

Answer 4

[OK]を、異なるものの束を試した後、ここに私のソリューションです。それはO(nlogn)時間で実行され、インターバルツリーを使用する必要はありません（私はインタビュー用のインプリメンテーションの実装方法を覚えることができますが、おそらくそれを使用しますが、利益）。

このアルゴリズムのボトルネックはソートにあります。すべての項目は一度だけタッチされますが、ソートされた配列でしか機能しませんので、これが最初に行うことです。従って、複雑さは時間の複雑さであるO(nlogn)です。オリジナルの配列を変更するので、O(1)の空間の複雑さがありますが、元の配列を変更することができない場合は、そのコピーを作成して残りのアルゴリズムを同じにしてスペースを作ります複雑度O(n)。

import java.util.*; 

class SmallestRangingSet { 
    static class Interval implements Comparable<Interval>{ 
     Integer min; 
     Integer max; 
     public Interval(int min, int max) { 
      this.min = min; 
      this.max = max; 
     } 

     boolean intersects(int num) { 
      return (min <= num && max >= num); 
     } 

     //Overrides the compareTo method so it will be sorted 
     //in order relative to the min value 
     @Override 
     public int compareTo(Interval obj) { 
      if (min > obj.min) return 1; 
      else if (min < obj.min) return -1; 
      else return 0; 
     } 
    } 

    public static Set<Interval> smallestIntervalSet(Interval[] set, Interval target) { 
     //Bottleneck is here. The array is sorted, giving this algorithm O(nlogn) time 
     Arrays.sort(set); 

     //Create a set to store our ranges in 
     Set<Interval> smallSet = new HashSet<Interval>(); 
     //Create a variable to keep track of the most optimal range, relative 
     //to the range before it, at all times. 
     Interval bestOfCurr = null; 
     //Keep track of the specific number that any given range will need to 
     //intersect with. Initialize it to the target-min-value. 
     int currBestNum = target.min; 
     //Go through each element in our sorted array. 
     for (int i = 0; i < set.length; i++) { 
      Interval currInterval = set[i]; 
      //If we have already passed our target max, break. 
      if (currBestNum >= target.max) 
       break; 
      //Otherwise, if the current interval intersects with 
      //our currBestNum 
      if (currInterval.intersects(currBestNum)) { 
       //If the current interval, which intersects currBestNum 
       //has a greater max, then our current bestOfCurr 
       //Update bestOfCurr to be equal to currInterval. 
       if (bestOfCurr == null || currInterval.max >= bestOfCurr.max) { 
        bestOfCurr = currInterval; 
       } 
      } 
      //If our range does not intersect, we can assume that the most recently 
      //updated bestOfCurr is probably the most optimal new range to add to 
      //our set. However, if bestOfCurr is null, it means it was never updated, 
      //because there is a gap somewhere when trying to fill our target range. 
      //So we must check for null first. 
      else if (bestOfCurr != null) { 
       //If it's not null, add bestOfCurr to our set 
       smallSet.add(bestOfCurr); 
       //Update currBestNum to look for intervals that 
       //intersect with bestOfCurr.max 
       currBestNum = bestOfCurr.max; 
       //This line is here because without it, it actually skips over 
       //the next Interval, which is problematic if your sorted array 
       //has two optimal Intervals next to eachother. 
       i--; 
       //set bestOfCurr to null, so that it won't run 
       //this section of code twice on the same Interval. 
       bestOfCurr = null; 
      } 

     } 

     //Now we should just make sure that we have in fact covered the entire 
     //target range. If we haven't, then we are going to return an empty list. 
     if (currBestNum < target.max) 
      smallSet.clear(); 
     return smallSet; 
    } 

    public static void main(String[] args) { 
     //{(1, 4), (30, 40), (20, 91) ,(8, 10), (6, 7), (3, 9), (9, 12), (11, 14)} 
     Interval[] interv = { 
       new Interval(1, 4), 
       new Interval(30, 40), 
       new Interval(20, 91), 
       new Interval(8, 10), 
       new Interval(6, 7), 
       new Interval(3, 9), 
       new Interval(9, 12), 
       new Interval(11, 14) 
     }; 
     Set<Interval> newSet = smallestIntervalSet(interv, new Interval(3,14)); 
     for (Interval intrv : newSet) { 
      System.out.print("(" + intrv.min + ", " + intrv.max + ") "); 
     } 

    } 
} 

出力

(3, 9) (9, 12) (11, 14)