javascript - 最长夜晚的最佳搜索算法 - Javascript

Question

给定一组酒店房间及其可用期(1 月 1 日至 1 月 6 日):

[
  {
    roomId: 101,
    availability: [
      { roomId: 101, date: '2018-01-01' },
      { roomId: 101, date: '2018-01-02' },
      { roomId: 101, date: '2018-01-03' },
      { roomId: 101, date: '2018-01-05' },
      { roomId: 101, date: '2018-01-06' }
    ]
  },
  {
    roomId: 102,
    availability: [
      { roomId: 102, date: '2018-01-01' },
      { roomId: 102, date: '2018-01-03' },
      { roomId: 102, date: '2018-01-04' },
      { roomId: 102, date: '2018-01-05' }
    ]
  },
  {
    roomId: 103,
    availability: [
      { roomId: 103, date: '2018-01-02' },
      { roomId: 103, date: '2018-01-03' },
      { roomId: 103, date: '2018-01-06' }
    ]
  },
  {
    roomId: 104,
    availability: [
      { roomId: 104, date: '2018-01-04' },
      { roomId: 104, date: '2018-01-05' },
      { roomId: 104, date: '2018-01-06' }
    ]
  },
  {
    roomId: 105,
    availability: [
      { roomId: 105, date: '2018-01-01' },
      { roomId: 105, date: '2018-01-02' },
      { roomId: 105, date: '2018-01-04' },
      { roomId: 105, date: '2018-01-06' }
    ]
  }
]

上面可用性的表格说明:

|     | 1 Jan | 2 Jan | 3 Jan | 4 Jan | 5 Jan | 6 Jan |
| 101 |   O   |   O   |   O   |       |   O   |   O   |
| 102 |   O   |       |   O   |   O   |   O   |       |
| 103 |       |   O   |   O   |       |       |   O   |
| 104 |       |       |       |   O   |   O   |   O   |
| 105 |   O   |   O   |       |   O   |       |   O   |

基于以上输入的预期结果是具有分组可用性的最终房间:

{
  roomId: 101, // determined by the first object in the array
  availability: [
    { roomId: 101, date: '2018-01-01' },
    { roomId: 101, date: '2018-01-02' },
    { roomId: 101, date: '2018-01-03' },
    { roomId: 104, date: '2018-01-04' },
    { roomId: 104, date: '2018-01-05' },
    { roomId: 104, date: '2018-01-06' }
  ]
}

Final grouping selection to be: 101 & 104

|     | 1 Jan | 2 Jan | 3 Jan | 4 Jan | 5 Jan | 6 Jan |
| 101 |  ✔️  |  ✔️   |  ✔️  |       |   O   |   O   |
| 102 |   O   |       |   O   |   O   |   O   |       |
| 103 |       |   O   |   O   |       |       |   O   |
| 104 |       |       |       |   ✔️  |  ✔️  |  ✔️  |
| 105 |   O   |   O   |       |   O   |       |   O   |

因此最终选择的确定方式是根据整个入住期间最少的房间移动

在 javascript 中执行此操作的最有效的搜索算法是什么(就性能而言) ？ (需要高效才能保持处理速度非常快，即使有很长时间的可用性请求或更多房间分组也是如此)

I'll put my algorithm in the answer section, but I don't think it is the most efficient way to do it. Please suggest if there is a better way!

Answer 1

我建议在几天内使用一个循环，并在每次迭代中，确定从当天开始连续开放时间最长的房间；然后，将天数增加该天数。

为了使解析更容易，您可以预处理数据，以便 可用性 信息在由 number 日期索引索引的对象中可用 - 例如，转

availability: [
  { roomId: 105, date: '2018-01-01' },
  { roomId: 105, date: '2018-01-02' },
  { roomId: 105, date: '2018-01-04' },
  { roomId: 105, date: '2018-01-06' }
]

进入

'105': {
  1: true,
  2: true,
  4: true,
  6: true
}

这样，要计算出房间 X 从第 N 天起可用多长时间，只需重复 rooms[x][n] === true 的测试并递增 n 直到测试失败。

如果多次执行此操作(从相同的房间数据集开始)，您可以提前一次进行所有实际计算，并构建一个包含最佳房间的对象以供选择每一天，例如:

{ // keys represent day index
  1: { roomId: 101, availableUntil: 3 },
  2: { roomId: 101, availableUntil: 3 }, // just as good as room 103
  3: { roomId: 101, availableUntil: 3 }, // just as good as 103 and 102
  // room 101 not available on Jan 4, room 104 becomes the best room to choose:
  4: { roomId: 104, availableUntil: 6 },
  5: { roomId: 104, availableUntil: 6 },
  6: { roomId: 104, availableUntil: 6 } // just as good as 105
}

然后，给定一个人希望停留的天数，计算破坏性最小的房间变化是一个简单的属性查找问题，直到到达结束日期。

为了简化以下代码的可读性，我将使用辅助函数

const dateStrToDayIndex = dateStr => Number(dateStr.match(/\d\d$/)[0]);

因此索引从 1 开始到 6，以测试您的输入，但在您的实际代码中，您当然会使用一些可靠的东西来计算 dateStr 和某个日期，例如 1970 年 1 月 1 日，或类似日期。 (或者，随意使用您当前正在使用的 moment(toDate).diff(moment(fromDate), 'days') 如果适合您的话)

现在，代码:首先将数据集转换为如下所示的对象:

/*
{
  101: {
    1: true,
    2: true,
    3: true,
    5: true,
    6: true,
  },
  102:
  // ...
}
*/
const dateStrToDayIndex = dateStr => Number(dateStr.match(/\d\d$/)[0]);

const datasetByRoom = dataset.reduce((datasetA, { roomId, availability }) => {
  datasetA[roomId] = availability.reduce((a, { date }) => {
    a[dateStrToDayIndex(date)] = true;
    return a;
  }, {});
  return datasetA;
}, {});

然后，主要的 getBestRoomFromDay 函数，需要一天索引并搜索 datasetByRoom 中的每个房间对象，从当前开始连续打开最多的房间日:

function getBestRoomFromDay(dayIndex) {
  let bestRoomSoFar;
  let bestCumulativeDaysSoFar = 0;
  Object.entries(datasetByRoom).forEach(([room, availObj]) => {
    let thisRoomDays = 0;
    let dayIndexCheck = dayIndex;
    while (availObj[dayIndexCheck]) {
      dayIndexCheck++;
      thisRoomDays++;
    }
    if (thisRoomDays > bestCumulativeDaysSoFar) {
      bestRoomSoFar = room;
      bestCumulativeDaysSoFar = thisRoomDays - 1;
    }
  });
  return {
    room: bestRoomSoFar,
    until: dayIndex + bestCumulativeDaysSoFar
  };
}

在实际操作中，为输入 (1-6) 中的每个 dayIndex 调用 getBestRoomFromDay 的示例:

const dataset=[{roomId:101,availability:[{roomId:101,date:'2018-01-01'},{roomId:101,date:'2018-01-02'},{roomId:101,date:'2018-01-03'},{roomId:101,date:'2018-01-05'},{roomId:101,date:'2018-01-06'}]},{roomId:102,availability:[{roomId:102,date:'2018-01-01'},{roomId:102,date:'2018-01-03'},{roomId:102,date:'2018-01-04'},{roomId:102,date:'2018-01-05'}]},{roomId:103,availability:[{roomId:103,date:'2018-01-02'},{roomId:103,date:'2018-01-03'},{roomId:103,date:'2018-01-06'}]},{roomId:104,availability:[{roomId:104,date:'2018-01-04'},{roomId:104,date:'2018-01-05'},{roomId:104,date:'2018-01-06'}]},{roomId:105,availability:[{roomId:105,date:'2018-01-01'},{roomId:105,date:'2018-01-02'},{roomId:105,date:'2018-01-04'},{roomId:105,date:'2018-01-06'}]}];const dateStrToDayIndex=dateStr=>Number(dateStr.match(/\d\d$/)[0]);const datasetByRoom=dataset.reduce((datasetA,{roomId,availability})=>{datasetA[roomId]=availability.reduce((a,{date})=>{a[dateStrToDayIndex(date)]=!0;return a},{});return datasetA},{});function getBestRoomFromDay(dayIndex){let bestRoomSoFar;let bestCumulativeDaysSoFar=0;Object.entries(datasetByRoom).forEach(([room,availObj])=>{let thisRoomDays=0;let dayIndexCheck=dayIndex;while(availObj[dayIndexCheck]){dayIndexCheck++;thisRoomDays++}
if(thisRoomDays>bestCumulativeDaysSoFar){bestRoomSoFar=room;bestCumulativeDaysSoFar=thisRoomDays-1}});return{room:bestRoomSoFar,until:dayIndex+bestCumulativeDaysSoFar}}

console.log('Example of testing getBestRoomFromDay function on all days:');
for (let i = 1; i < 7; i++) {
  console.log('Day ' + i + ': ' + JSON.stringify(getBestRoomFromDay(i)));
}

然后，从 from 和 to 日期字符串构造一个时间表，例如 '2018-01-01' 到 '2018-01-06'，只需用适当的日期重复调用 getBestRoomFromDay，在每次迭代中将日期索引增加所需的数量:

const dataset=[{roomId:101,availability:[{roomId:101,date:'2018-01-01'},{roomId:101,date:'2018-01-02'},{roomId:101,date:'2018-01-03'},{roomId:101,date:'2018-01-05'},{roomId:101,date:'2018-01-06'}]},{roomId:102,availability:[{roomId:102,date:'2018-01-01'},{roomId:102,date:'2018-01-03'},{roomId:102,date:'2018-01-04'},{roomId:102,date:'2018-01-05'}]},{roomId:103,availability:[{roomId:103,date:'2018-01-02'},{roomId:103,date:'2018-01-03'},{roomId:103,date:'2018-01-06'}]},{roomId:104,availability:[{roomId:104,date:'2018-01-04'},{roomId:104,date:'2018-01-05'},{roomId:104,date:'2018-01-06'}]},{roomId:105,availability:[{roomId:105,date:'2018-01-01'},{roomId:105,date:'2018-01-02'},{roomId:105,date:'2018-01-04'},{roomId:105,date:'2018-01-06'}]}];const dateStrToDayIndex=dateStr=>Number(dateStr.match(/\d\d$/)[0]);const datasetByRoom=dataset.reduce((datasetA,{roomId,availability})=>{datasetA[roomId]=availability.reduce((a,{date})=>{a[dateStrToDayIndex(date)]=!0;return a},{});return datasetA},{});function getBestRoomFromDay(dayIndex){let bestRoomSoFar;let bestCumulativeDaysSoFar=0;Object.entries(datasetByRoom).forEach(([room,availObj])=>{let thisRoomDays=0;let dayIndexCheck=dayIndex;while(availObj[dayIndexCheck]){dayIndexCheck++;thisRoomDays++}
if(thisRoomDays>bestCumulativeDaysSoFar){bestRoomSoFar=room;bestCumulativeDaysSoFar=thisRoomDays-1}});return{room:bestRoomSoFar,until:dayIndex+bestCumulativeDaysSoFar}};

function getSchedule(dateStrFrom, dateStrTo) {
  const [from, to] = [dateStrFrom, dateStrTo].map(dateStrToDayIndex);
  let day = from;
  const schedule = [];
  while (day < to) {
    const schedObj = getBestRoomFromDay(day);
    schedule.push({ from: day, ...schedObj });
    // increment day, so as to find the next longest consecutive room:
    day = schedObj.until + 1;
  }
  schedule[schedule.length - 1].until = to;
  return schedule;
}
console.log(getSchedule('2018-01-01', '2018-01-06'));

完整的，未缩小的:

const dataset = [
  {
    roomId: 101,
    availability: [
      { roomId: 101, date: '2018-01-01' },
      { roomId: 101, date: '2018-01-02' },
      { roomId: 101, date: '2018-01-03' },
      { roomId: 101, date: '2018-01-05' },
      { roomId: 101, date: '2018-01-06' }
    ]
  },
  {
    roomId: 102,
    availability: [
      { roomId: 102, date: '2018-01-01' },
      { roomId: 102, date: '2018-01-03' },
      { roomId: 102, date: '2018-01-04' },
      { roomId: 102, date: '2018-01-05' }
    ]
  },
  {
    roomId: 103,
    availability: [
      { roomId: 103, date: '2018-01-02' },
      { roomId: 103, date: '2018-01-03' },
      { roomId: 103, date: '2018-01-06' }
    ]
  },
  {
    roomId: 104,
    availability: [
      { roomId: 104, date: '2018-01-04' },
      { roomId: 104, date: '2018-01-05' },
      { roomId: 104, date: '2018-01-06' }
    ]
  },
  {
    roomId: 105,
    availability: [
      { roomId: 105, date: '2018-01-01' },
      { roomId: 105, date: '2018-01-02' },
      { roomId: 105, date: '2018-01-04' },
      { roomId: 105, date: '2018-01-06' }
    ]
  }
];
const dateStrToDayIndex = dateStr => Number(dateStr.match(/\d\d$/)[0]);

const datasetByRoom = dataset.reduce((datasetA, { roomId, availability }) => {
  datasetA[roomId] = availability.reduce((a, { date }) => {
    a[dateStrToDayIndex(date)] = true;
    return a;
  }, {});
  return datasetA;
}, {});

function getBestRoomFromDay(dayIndex) {
  let bestRoomSoFar;
  let bestCumulativeDaysSoFar = 0;
  Object.entries(datasetByRoom).forEach(([room, availObj]) => {
    let thisRoomDays = 0;
    let dayIndexCheck = dayIndex;
    while (availObj[dayIndexCheck]) {
      dayIndexCheck++;
      thisRoomDays++;
    }
    if (thisRoomDays > bestCumulativeDaysSoFar) {
      bestRoomSoFar = room;
      bestCumulativeDaysSoFar = thisRoomDays - 1;
    }
  });
  return {
    room: bestRoomSoFar,
    until: dayIndex + bestCumulativeDaysSoFar
  };
}

function getSchedule(dateStrFrom, dateStrTo) {
  const [from, to] = [dateStrFrom, dateStrTo].map(dateStrToDayIndex);
  let day = from;
  const schedule = [];
  while (day < to) {
    const schedObj = getBestRoomFromDay(day);
    schedule.push({ from: day, ...schedObj });
    // increment day, so as to find the next longest consecutive room:
    day = schedObj.until + 1;
  }
  schedule[schedule.length - 1].until = to;
  return schedule;
}
console.log(getSchedule('2018-01-01', '2018-01-06'));

如前所述，如果您必须从相同数据集计算多个getBestRoomFromDay(即，不插入新预订)，您可以构造一个对象预先包含 getBestRoomFromDay 的每个可能的值，它可以被调用，从而确保每天的计算只会一次。