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

给定一系列酒店房间及其有效期(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   |

根据上面的输入，预期结果是具有分组可用性的最终 session 室:

{
  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' }
  ]
}

|     | 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中执行此操作的最有效的搜索算法是什么？ (即使在长期要求可用性或将更多房间分组的情况下，也需要有效保持真正快速的处理)

最佳答案

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

为了简化解析，您可以对数据进行预处理，以便在由数字日期索引索引的对象中可以使用availability信息-例如，将

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
}

这样，要弄清楚从第N天起房间X可用的时间，只需重复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
}

然后，在输入了想要停留的天数之后，计算最不具破坏性的房间变化是属性(property)查询的简单问题，直到到达结束日期为止。

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

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
  };
}

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

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的值，因此确保每天只计算一次。