【JavaScript】1つの範囲に含まれる複数の範囲の合計を求めるアルゴリズム

問題の概要

ここでは、2種類の範囲(レンジ)を扱います。1つは任意の長さを持つ単一の範囲 R1、もう1つは複数の範囲からなる集合 R2 です。R2 に含まれる各範囲は、R1 に完全に収まることもあれば、一部だけが重なることも、まったく重ならないこともあります。

目的は、R2 の各範囲のうち R1 と重なっている部分(全体または一部)の長さをすべて合計することです。

入力例 1

const R1 = [20,40];
const R2 = [[14,22],[24,27],[31,35],[38,56]];

結果

= 2+3+4+2 = 11

[14,22] は R1=[20,40] との重なりが 20〜22 のため長さは 2。同様に [24,27] は 3、[31,35] は 4、[38,56] は 38〜40 の部分のみ重なり長さ 2 となります。これらを合計すると 11 が答えです。

入力例 2

R1 = [120,356];
R2 = [[234,567]];

結果

122

[234,567] は R1 と 234〜356 の区間でのみ重なるため、その長さ 122 が答えになります。

実装例

それでは、実際のコードを見てみましょう。

const R1 = [20,40];
const R2 = [[14,22],[24,27],[31,35],[38,56]];
const R3 = [120,356];
const R4 = [[234,567]];
function sumRanges(range, values) {
    const [start, end] = range;
    const res = values.reduce((acc, val) => {
        const [left, right] = val;
        const ex1 = Math.min(right, end);
        const ex2 = Math.max(left, start);
        const diff = ex1 - ex2;
        return acc + Math.max(0, diff);
    }, 0);
    return res;
};
console.log(sumRanges(R1, R2));
console.log(sumRanges(R3, R4));

コードの解説

このアルゴリズムのポイントは以下のとおりです。

• まず、基準となる範囲 range を start(始点)と end(終点)に分解します。
• reduce を使い、values 内の各範囲 [left, right] を順番に処理していきます。
• 重なり区間の右端は Math.min(right, end)、左端は Math.max(left, start) で求められます。
• 両者の差 diff が正であれば、それが実際の重なり(交差)の長さです。
• diff が負になる場合、つまり範囲がまったく重ならない場合は Math.max(0, diff) によって 0 として扱われ、合計に影響しません。

出力結果

コンソールには次のように出力されます。

11
122

まとめ

Math.min と Math.max を組み合わせて交差区間を求め、負の値を 0 に丸めることで、複雑な if 文による条件分岐を書かずに「範囲の重なり合計」を簡潔に計算できます。この手法は、予約時間帯の重複集計やデータ区間のフィルタリングなど、さまざまな場面で応用できる汎用的なパターンなので、ぜひ覚えておきましょう。