ここで私が聞いたインタビューの質問です。配列の範囲は、要素が長さ2の配列であり、始点と終点が番号の行にあります。重複がある可能性があります。あなたがカバーする総距離を返す必要があります。これをどうやって解決しますか？範囲の配列が与えられている場合、総距離はカバーされていますか？
例： 入力：[[3,5], [1,3], [2,4]] 出力：4つの
私の考え：あなたが覆われていた範囲何と値が特定の範囲にあった場合を追跡する必要があると思います。しかし、それをどうやって行うのか本当に分かりませんか？
これは私の実装です。
すべての範囲に最小値と最大値があります（| min | ------ | max |） ソートリストがある場合は、最後の最大値からの現在の最小値。その値が負の値の場合、2つの範囲に違いは見られません。したがって、その範囲を含める必要はなく、新しい最大値を保存するだけです。
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));
}
}
開始間隔をマージする必要があります。一度マージされると、各間隔でカバーされた距離の合計として合計距離が計算されます。
間隔をO(n * log n)にマージできます.nは間隔の数です。これを行うには、最初のポイント/ 2番目のポイントに基づいてソートします。今度はソートされた区間を繰り返し、どの区間をマージするかをチェックします。なぜ、どのようにマージできるのかを理解するには、
a---------------------b
c-------------------d
のようになり、マージされた間隔の類似性に気づくでしょう。ヒントmax(a,c) > min(b,d)。
P.S.インタビューに合格するには、その質問についてもっと考えることが理にかなっています。
これは私が（ソート）
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