Middle+

Dans le prototype du réseau de vente publicitaire, la vente d'espaces publicitaires est organisée comme suit : les acheteurs indiquent leur prix à l'avance, et pour chaque espace publicitaire, ils répondent s'ils sont prêts à l'acheter ou non. Il est nécessaire d'implémenter une fonction qui, avant de vendre un espace publicitaire, attend l'accord ou le refus des acheteurs avec la plus haute offre, puis vend l'espace à l'acheteur avec la plus haute offre parmi ceux qui ont accepté. La réponse de la fonction doit être aussi rapide que possible. Elle doit retourner l'indice de l'acheteur. Exemples : Les acheteurs proposent des prix 1, 5, 10 L'acheteur avec l'offre 10 a répondu par un refus L'acheteur avec l'offre 1 a répondu par un accord // Nous attendons encore, car l'acheteur avec l'offre 5 peut répondre L'acheteur avec l'offre 5 a répondu par un accord // Nous choisissons l'acheteur avec l'offre 5 ------------ Les acheteurs proposent des prix 1, 5, 10 L'acheteur avec l'offre 10 a répondu par un refus L'acheteur avec l'offre 5 a répondu par un accord // Nous n'attendons pas la réponse de l'acheteur avec l'offre 1 - il ne sera pas choisi ------------ Les acheteurs proposent des prix 1, 2 L'acheteur avec l'offre 1 a répondu par un refus L'acheteur avec l'offre 2 a répondu par un refus // Aucun acheteur n'est choisi type Buyer = { price: number, accepts: () => Promise<boolean>, } async function bestBuyer(buyers) { const sorted = buyers.map((buyer, index) => ({buyer, index})) .sort((a, b) => a.buyer.price - b.buyer.price); const promise = sorted.map(({buyer}) => buyer.accepts()); for (let i = 0; i < sorted.length; i++) { const accepted = await promise[i]; if (accepted) { return sorted[i].index; } } if (await buyers[0].accepts()) { return 0; } return -1; }

sobes.tech IA

Réponse de l'IA

Ваша задача — как можно быстрее определить покупателя с максимальной ценой, который согласился купить рекламное место. При этом ответы покупателей приходят асинхронно и могут быть в любом порядке.

Основная идея решения:

Отсортировать покупателей по цене по убыванию — от самого дорогого к дешевому.
Запустить параллельно все промисы accepts().
Обрабатывать ответы в порядке убывания цены, чтобы как только самый дорогой покупатель согласится, сразу вернуть его индекс.
Если самый дорогой отказался, ждать ответа следующего по цене и так далее.

Это позволит не ждать всех ответов, а вернуть результат как можно раньше.

Пример реализации:

async function bestBuyer(buyers) {
  // Сортируем по убыванию цены
  const sorted = buyers
    .map((buyer, index) => ({ buyer, index }))
    .sort((a, b) => b.buyer.price - a.buyer.price);

  // Запускаем все промисы параллельно
  const acceptPromises = sorted.map(({ buyer }) => buyer.accepts());

  for (let i = 0; i < sorted.length; i++) {
    const accepted = await acceptPromises[i];
    if (accepted) {
      // Возвращаем индекс покупателя с самой высокой ценой, который согласился
      return sorted[i].index;
    }
  }

  // Если никто не согласился
  return -1;
}

Таким образом, мы не ждём ответы покупателей с меньшей ценой, если уже получили согласие от более дорогого покупателя. Это ускоряет получение результата.

Précédent Suivant