Middle+

Σε ένα πρωτότυπο δικτύου διαφήμισης, η πώληση διαφημιστικών χώρων λειτουργεί ως εξής: οι αγοραστές δηλώνουν εκ των προτέρων την τιμή τους, και για κάθε διαφημιστικό χώρο απαντούν αν είναι διατεθειμένοι να τον αγοράσουν ή όχι. Είναι απαραίτητο να υλοποιηθεί μια λειτουργία που, πριν πουλήσει έναν διαφημιστικό χώρο, θα περιμένει την αποδοχή ή την άρνηση των αγοραστών με την υψηλότερη προσφορά, και στη συνέχεια θα πουλήσει τον χώρο στον αγοραστή με την υψηλότερη προσφορά από αυτούς που αποδέχθηκαν. Η απάντηση της λειτουργίας πρέπει να επιστραφεί όσο το δυνατόν πιο γρήγορα. Πρέπει να επιστρέψει το δείκτη του αγοραστή. Παραδείγματα: Οι αγοραστές προτείνουν τιμές 1, 5, 10 Ο αγοραστής με προσφορά 10 απάντησε αρνητικά Ο αγοραστής με προσφορά 1 απάντησε θετικά // Ακόμα περιμένουμε, επειδή μπορεί να απαντήσει ο αγοραστής με τιμή 5 Ο αγοραστής με προσφορά 5 απάντησε θετικά // Επιλέγουμε τον αγοραστή με την προσφορά 5 ------------ Οι αγοραστές προτείνουν τιμές 1, 5, 10 Ο αγοραστής με προσφορά 10 απάντησε αρνητικά Ο αγοραστής με προσφορά 5 απάντησε θετικά // Δεν περιμένουμε απάντηση από τον αγοραστή με προσφορά 1 - σίγουρα δεν θα επιλεγεί ------------ Οι αγοραστές προτείνουν τιμές 1, 2 Ο αγοραστής με προσφορά 1 απάντησε αρνητικά Ο αγοραστής με προσφορά 2 απάντησε αρνητικά // Δεν επιλέγουμε κανέναν interface 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 AI

Απάντηση από AI

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

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

Отсортировать покупателей по цене по убыванию — от самого дорогого к дешевому.
Запустить параллельно все промисы 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;
}

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

Προηγούμενος Επόμενο