Angesichts einer Reihe von Bereichen finden Sie die gesamte zurückgelegte Strecke?

Question

Hier ist eine Interviewfrage, von der ich gehört habe. Sie haben eine Reihe von Arrays, bei denen die Elemente Länge zwei Arrays mit einem Startpunkt und einem Endpunkt auf einer Zahlenzeile sind. Es kann Überschneidungen geben. Sie müssen die gesamte zurückgelegte Strecke zurückgeben. Wie würdest du das lösen?

Beispiel: Eingang: [[3,5], [1,3], [2,4]] Ausgang: 4

Meine Gedanken: Sie müssen, um zu verfolgen, was abgedeckt wurden Bereiche und wenn ein Wert war in einem bestimmten Bereich. Nicht wirklich sicher, wie man das tut, obwohl?

Answer 1

Hier ist meine Implementierung.
Da jeder Bereich einen minimalen Wert und einen maximalen Wert hat (| min | ------ | max |) Wenn Sie eine sortierte Liste haben, können Sie die Entfernung finden, die nicht durch Subtrahieren der aktuelle min von der letzten max. Wenn dieser Wert negativ ist, wissen Sie, dass zwischen den beiden Bereichen kein Unterschied gefunden wurde. Sie müssen also diesen Bereich nicht einschließen, speichern Sie einfach das neue Maximum.

import java.util.ArrayList; 
import java.util.HashMap; 

public class Main { 
    public static void main(String[] args) { 
     //GIVEN A SORTED ARRAY BY THE INDEX AT 0 
     // (equal array[0] is then sorted by array[1]. 
     //If array isn't sorted you sort it here 

     ArrayList<int[]> ranges = new ArrayList<>(); 
     ranges.add(new int[]{1,3}); 
     ranges.add(new int[]{2,4}); 
     ranges.add(new int[]{3,5}); 

     //getSortedArray(ranges); //not implemented here 

     int min = ranges.get(0)[0]; 
     int totalDifference = 0; 
     int lastMax = 0; 

     int MAX = 0; 
     for(int i = 0; i < ranges.size(); i++){ 
      if(i == 0){ 
       //the highest max is the current index at 1 
       lastMax = ranges.get(i)[1]; 
      }else{ 
       int tempMin = ranges.get(i)[0]; 
       int diff = (tempMin - lastMax); 
       //Only if the range is above the last range. 
       // A negative means there is no difference. 
       if(diff > 0) { 
        //Subtract the new min of the range from the last max 
        // This gives you the distance between ranges. 
        totalDifference += diff; 
       } 
       lastMax = ranges.get(i)[1]; // Set the new last max 
      } 
      MAX = ranges.get(i)[1]; 
     } 
     System.out.println("Total Distance = " + (MAX - min - totalDifference)); 
    } 
} 

Answer 2

Sie müssen die Anfangsintervalle zusammenführen und nach der Zusammenführung berechnen Sie die Gesamtstrecke als Summe der in jedem Intervall zurückgelegten Entfernungen.

Sie können Intervalle in O(n * log n) zusammenführen, wobei n die Anzahl der Intervalle ist. Um dies zu tun, sortieren Sie sie basierend auf dem ersten Punkt/zweiten Punkt. Jetzt iterieren Sie über die sortierten Intervalle und prüfen, welcher zusammengeführt werden soll. Um zu verstehen, warum und wie sie zusammengeführt werden können, zeichnen Sie etwas wie folgt:

und beachten Sie die Ähnlichkeit der zusammengeführten Intervalle. Tipp max(a,c) > min(b,d).

P.S. Wenn Sie ein Interview bestehen möchten, ist es sinnvoll, mehr über die Frage nachzudenken.

Answer 3

Dies ist, wie ich es gelöst (sortiert)

def total_distance(intervals) 
    distance = 0 
    max_value = nil 
    intervals.each do |array| 
    if max_value.nil? 
     distance += array[1] - array[0] 
     max_value = array[1] 
    elsif array[0] < max_value && array[1] < max_value 
     next 
    elsif array[0] < max_value && array[1] > max_value 
     distance += array[1] - max_value 
     max_value = array[1] 
    elsif array[0] > max_value 
     distance += array[1] - array[0] 
     max_value = array[1] 
    end 
    end 
    distance 
end 

p total_distance([[1,5], [2,3], [4,8]]) == 7 
p total_distance([[1,2], [3,4], [5,6]]) == 3