Mit einer Reihe von Bereichen S und einem überlappenden Bereich R, finden Sie die kleinste Teilmenge in S, die umfasst R

Question

Das folgende ist eine Praxis Interview Frage, die mir von jemandem gegeben wurde, und ich bin mir nicht sicher, was die beste Lösung dazu ist:

eine Reihe von Bereichen gegeben:
(zB S = {(1, 4), (30, 40), (20, 91) ,(8, 10), (6, 7), (3, 9), (9, 12), (11, 14)} Und ein Zielbereich R gegeben (zB R = (3, 13) - also die 3-13 gehen Bereich) einen Algorithmus schreiben.. Finde den kleinsten Satz von Bereichen, die deinen Zielbereich abdecken Alle Bereiche in dem Satz müssen sich überlappen, um als Spannweite zu gelten der gesamte Zielbereich. (In diesem Beispiel würde die Antwort {(3, 9), (9, 12), (11, 14)} sein.

Was ist der beste Weg, dies zu lösen? Ich habe nachgedacht getan werden würde einen Greedy-Algorithmus verwendet wird. In unserem Beispiel oben, würden wir für alle aussehen von den Zahlen, die sich mit 3 schneiden, und wählen aus denen die mit dem höchsten Max. Dann würden wir dasselbe mit dem tun, was wir gerade ausgewählt haben, also, da wir (3, 9) ausgewählt haben, wollen wir nun alle finden die Bereiche, die 9 schneiden, und unter denen wählen wir den mit dem höchsten Max. In dieser Iteration haben wir (9, 12) gewählt.Wir machen dasselbe mit dem, und wir finden, dass der nächste Bereich 12 schneidet , mit dem höchsten max ist (11, 14).

Nach dieser Iteration sehen wir, dass 14 größer als 13 ist (das Maximum unserer Reichweite), damit wir aufhören können.

Das Problem, das ich mit diesem Algorithmus habe, ist, wie effizient die überschneidenden Bereiche abfragen? Wenn wir eine lineare Suche versuchen, erhalten wir einen Algorithmus, der O(n^2) ist. Mein nächster Gedanke war, jeden unserer überschneidenden Bereiche aus unserer Liste zu streichen, wenn wir die Schleife durchlaufen. Also kreuzen wir in der ersten Iteration (1, 4) und (3, 9). In unserer nächsten Iteration kreuzen wir (9, 12), (3, 9) und (8, 10). Bei der letzten Iteration müssen wir also nur durchsehen: {(30, 40), (20, 91), (6, 7)}. Wir könnten dies noch effizienter machen, indem wir auch alles ausstreichen, was ein Minimum von> 13 und ein Maximum von < 3 hat. Das Problem ist, dass dies immer noch nicht genug ist. Es gibt immer noch das potentielle Problem, viele Doppelsequenzen im Rahmen unseres Angebots zu haben. Wenn unsere Liste von Bereichen etwas wie {(6, 7), (6, 7), (6, 7), (6, 7), (6, 7)} enthalten würde, müssten wir jedes Mal durch diese Liste schauen , obwohl sie uns nicht nützlich sind. Selbst wenn wir nur eindeutige Werte speichern sollten (indem wir sie alle in ein Set setzen), haben wir vielleicht eine sehr große Auswahl, mit einer Reihe von Bereichen, die innerhalb unseres Zielbereichs liegen, aber wir haben auch einen Bereich, der sich fast überspannt der gesamte Zielbereich.

Was wäre eine effiziente Möglichkeit, unsere Sortimente abzufragen? Oder möglicherweise, was wäre ein effizienterer Algorithmus zur Lösung dieses Problems?

Answer 1

Wie wäre es mit einem Intervallbaum für Abfragen? (https://en.m.wikipedia.org/wiki/Interval_tree) Ich bin mir nicht sicher, ob gierige hier arbeiten könnte oder nicht.Wenn wir in der letzten Reihe von Optionen aussehen, mit dem Höhepunkt überlappend in R, gibt es eine Möglichkeit der Überlappung zwischen den früheren Entscheidungen für jeden von denen, zum Beispiel:

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

In diesem Fall werden wir nur brauchen um einen Wert für (6,8) als ein zweites Bein des Pfades zu speichern; und wieder (6,8) zu besuchen, wie wir längere Wege in Richtung der Tiefpunkt in R machen würde überflüssig sein, da wir bereits wissen (6,8) wurde mit einer unteren Beinzahl besucht. Ihre Idee, Intervalle zu eliminieren, macht Sinn. Könnte so etwas funktionieren?

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

Ich kann folgenden Algorithmus mit Komplexität O(n log n) vorschlagen, ohne Intervalle Bäume zu verwenden.

Lassen Sie einige Notation vorstellen. Wir sollten einen Bereich (X,Y) durch Intervalle (x_i,y_i) abdecken.

Erste sortierte Intervalle (x_i,y_i) nach Startpunkt. Es dauert O(n log n)

von Intervallen (x_i,y_i) mit x_i <= X Intervall (x_k,y_k) mit maximal y_i wählen zu lassen. Da das Intervall bereits nach dem Startpunkt sortiert ist, können wir nur den Index erhöhen, während das Intervall die Bedingung erfüllt. Wenn y_k weniger als X ist, gibt es keine Lösung für gegebene Menge und Bereich. In anderen Fällen enthält das Intervall (x_k,y_k) 'X' und hat den maximalen Endpunkt zwischen den Intervallen, die X enthalten.

Jetzt müssen wir ein Intervall (y_k, Y) abdecken, überlappenden Zustand zu erfüllen. Da für alle Intervalle, die X enthalten, der Endpunkt kleiner als y_k+1 ist, können wir vom letzten Intervall des vorherigen Schritts aus beginnen.

Jedes Intervall wurde nur einmal in dieser Phase verwendet, daher ist die Zeitkomplexität dieses Teils O(n) und insgesamt O(n log n).

folgende Code-Schnipsel für Lösung:

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

Ihre Aufgabe fasziniert mich, so schrieb ich ein C++ Programm, das durch Iteration durch die Bereiche löst das Problem, dass die linke Seite des Zielbereichs überlappen, und rekursiv durchsucht für die kleinste Anzahl von Bereichen, die die verbleibende (rechte Seite) des Zielbereichs abdecken. Eine signifikante Optimierung dieses Algorithmus (in diesem Programm nicht gezeigt) würde darin bestehen, für jede rekursive Ebene den Bereich zu verwenden, der die linke Seite des Zielbereichs um den größten Betrag überlappt, und alle Bereiche von der weiteren Betrachtung auszuschließen die die linke Seite um kleinere Beträge überlappen. Mit dieser Regel glaube ich, dass es höchstens einen einzigen Abstieg in den rekursiven Aufrufbaum geben würde. Eine solche Optimierung würde einen Algorithmus mit der Komplexität 0 (n log (n)) erzeugen. (n, um die Tiefe der Rekursion zu berücksichtigen, und log (n), um die binäre Suche zu berücksichtigen, um den Bereich mit der größten Überlappung zu finden.

)

Dieses Programm erzeugt die folgende als Ausgabe:

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

Hier ist das Programm:

#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, nach ein paar verschiedene Dinge versuchen, hier ist meine Lösung. Es läuft in O(nlogn) Zeit, und erfordert nicht die Verwendung eines Interval Tree (obwohl ich es wahrscheinlich verwenden würde, wenn ich auswendig lernen könnte, wie man für ein Interview zu implementieren, aber ich denke, dass würde zu lange dauern, ohne wirklich zu liefern Vorteil).

Der Flaschenhals dieses Algorithmus ist in der Sortierung. Jedes Element wird nur einmal berührt, aber es funktioniert nur mit einem sortierten Array, das ist das erste, was wir tun. So ist die Komplexität der Zeit. O(nlogn). Da es das ursprüngliche Array ändert, hat es eine O(1) Raum-Komplexität, aber wenn wir nicht das Original-Array ändern durften, können wir nur eine Kopie davon machen und den Rest des Algorithmus gleich halten, wodurch der Raum entsteht Komplexität 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 + ") "); 
     } 

    } 
} 

Ausgabe

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