Alle Herausforderungen
Schwierig 1 gelöst 100.0% Erfolgsquote

Minimum Elevator Rides

Group people into as few weight-limited elevator rides as possible.

Das lernst du

  • Represent groups of people as bitmasks
  • Store the best rides and last ride weight per subset
  • Handle exponential search spaces cleverly

Problem

Übersetzung anzeigen

Each person must ride exactly once. Any group can share a ride if the sum of its weights is no greater than capacity. People may be regrouped freely; their input order does not matter. Minimize the number of rides.

Implement elevator_rides(weights, capacity).

Input

weights: The weight of each person.

capacity: The maximum combined weight in a ride.

Output

Return the minimum number of rides.

Einschränkungen

1 ≤ people ≤ 20. 1 ≤ capacity ≤ 1,000,000,000. Every weight is between 1 and capacity.

Beispiele

Beispiel 1
Eingabe:
weights = [3, 4, 5]
capacity = 7

Erwartete Ausgabe:
expected = 2
Eingabe:
std::vector<long long> weights = {3, 4, 5};
long long capacity = 7;

Erwartete Ausgabe:
long long expected = 2;
Eingabe:
long[] weights = new long[] {3, 4, 5};
long capacity = 7;

Erwartete Ausgabe:
long expected = 2;

Erläuterung

Send 3 + 4 together and 5 separately. Total weight 12 cannot fit in one ride of capacity 7.

Beispiel 2
Eingabe:
weights = [2, 2, 2]
capacity = 6

Erwartete Ausgabe:
expected = 1
Eingabe:
std::vector<long long> weights = {2, 2, 2};
long long capacity = 6;

Erwartete Ausgabe:
long long expected = 1;
Eingabe:
long[] weights = new long[] {2, 2, 2};
long capacity = 6;

Erwartete Ausgabe:
long expected = 1;

Erläuterung

All three people fit together because 2 + 2 + 2 = 6.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Since the number of people is small, consider subsets rather than individual rides.

Hinweis 2

Track both how many rides are used and how full the current last ride is for each subset.

Hinweis 3

When two states use the same number of rides, prefer the one with smaller current load.

Erwartete Komplexität

O(2^n * n) time, O(2^n) extra space

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 ННикита Python 831 ms - 4/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 1 vollständige Lösung unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.