JavaScriptのHackerrankサービスレーン問題の解法

総当たり法: この方法では、指定された範囲内の各車両の幅を比較し、最小幅を見つけます。以下はJavaScriptでのコード例です。

function serviceLane(width, cases) {
 const result = [];
 for (let i = 0; i < cases.length; i++) {
   const [start, end] = cases[i];
   let min = Infinity;
   for (let j = start; j <= end; j++) {
     if (width[j] < min) {
       min = width[j];
     }
   }
   result.push(min);
 }
 return result;
}

前処理と動的計画法: この方法では、道路の幅を前処理しておき、各範囲の最小幅を効率的に求めます。以下はJavaScriptでのコード例です。

function preprocess(width) {
 const dp = [0];
 for (let i = 1; i < width.length; i++) {
   dp[i] = Math.min(dp[i - 1], width[i]);
 }
 return dp;
}
function serviceLane(width, cases) {
 const result = [];
 const dp = preprocess(width);
 for (let i = 0; i < cases.length; i++) {
   const [start, end] = cases[i];
   result.push(dp[end] - dp[start - 1]);
 }
 return result;
}