使用数组字符串寻找性能可行性

Question

这是要求的详细信息：

time = ["09-13", "12-14"]

getResult(time) = false

首场演出从 9 a.m 开始。到 1 p.m。第二个从 12 p.m 开始。所以您将无法完整地看到每场演出。

time = ["07-09", "10-12", "15-19"]

getResult(time) = true

但我无法得到结果。我正在寻找挑战来完成它。有人帮帮我吗？

这是我的尝试：

const getResult = (time) => {
  const nums = [];
  let pre = 0;
  time.map((item,index) => {
    item.split('-').map((v,i) => {
      nums.push(+v);//converting as number
    });
  });
  const result = nums.map((v,i) => {
    if(!i) return;
    console.log(v-pre)//but logically this is not works
    pre = v;
  })
}

//time = ["09-13", "12-14"]; //false
time = ["07-09", "10-12", "15-19"] //true
getResult(time); //should be false

提前致谢。

Answer 1

将每个范围转换为范围内的每个小时，然后：

如果小时已经存在于数组中，return false
否则，推送到数组

const getResult = (ranges) => {
  const filled = [];
  for (const range of ranges) {
    let [start, end] = range.split('-').map(Number);
    while (end !== start) { // Exclusive
      if (filled.includes(start)) return false;
      filled.push(start);
      start++;
    }
  }
  return true;
};
console.log(getResult(["09-13", "12-14"]));
console.log(getResult(["07-09", "10-12", "15-19"]));

您当前的方法看起来没有任何将范围转换为各自小时数或识别重叠的概念。

Answer 2

根据开始时间对时间段进行排序。
遍历排序数组中的所有时隙，如果任何时候一个时隙的开始小于前一个时隙的结束，则 return false.
如果整个循环都用完了return true.

function isValid(time) {
  const sortedTime = [...time].sort((a, b) => {
    const slotA = Number(a.split("-")[0]);
    const slotB = Number(b.split("-")[0]);
    return slotA - slotB;
  });

  let last;
  for (let t of sortedTime) {
    const [start, end] = t.split("-").map(Number);
    if (last && start < last) {
      return false;
    }
    last = end;
  }
  return true;
}

console.log(isValid(["12-14", "09-13"]));
console.log(isValid(["10-12", "07-09", "15-19"]));

Answer 3

您的格式已经可用于直接 >= 比较，一旦我们将值拆分为 -。所以我们可以简单地对值进行排序，然后检查在第一个之后的每种情况下，开始部分（- 之前）至少与结束部分（- 之后）一样大以前的价值。它可能看起来像这样：

const feasible = (times) => [... times] 
  .sort () 
  .every ((t, i, a) => i == 0 || t .split ('-') [0] >= a [i - 1] .split ('-') [1])  


console .log (feasible (["09-13", "12-14"]))
console .log (feasible (["07-09", "10-12", "15-19"]))

我们使用 i == 0 || 来简单地避免测试第一个排序值。

这涉及将每个值拆分两次（嗯，除了第一个。）如果这种低效率困扰您，我们可以通过拆分它们并保存结果来解决它（使用更多内存；总是需要权衡！） :

const feasible = (times) => [... times] 
  .sort () 
  .map (s => s .split ('-')) 
  .every ((t, i, a) => i == 0 || t [0] >= a [i - 1]  [1])

使用数组字符串寻找性能可行性

Finding performance feasibility using array strings

javascript

arrays

algorithm