Frontend School

Optimized Shipment Container Loading

DSA
medium

Optimized Shipment Container Loading

Medium
Queue
Greedy
Arrays
Logistics

Overview

In a bustling Shiprocket logistics hub, efficient container loading is paramount for timely deliveries and optimal resource utilization. Parcels arrive continuously and need to be grouped into outgoing containers, each with a specific weight capacity. Crucially, some parcels are marked as "priority" and require preferential treatment. This problem challenges you to design a system that intelligently loads parcels into containers, prioritizing urgent shipments while maximizing container utilization and strictly adhering to weight limits.

What you need to do / Task

Your task is to implement a function that simulates the process of loading parcels into containers based on their arrival order, weight, and priority status.

  1. Implement a function loadContainers that takes an array of Parcel objects and the maxWeightCapacity of a single container.
  2. The function should simulate loading parcels into containers. Parcels are processed in their order of appearance in the input parcels array.
  3. When filling a container, priority parcels (isPriority = true) should always be considered for loading before non-priority parcels, as long as they fit into the current container. Among fitting priority parcels, pick the one that arrived earliest.
  4. If a priority parcel cannot fit into the current container, it should remain in its waiting list and wait for the next available space (either in the current container if other smaller parcels are loaded first, or in a new container).
  5. If no more priority parcels can be loaded into the current container, then consider loading standard parcels (isPriority = false) that fit, again picking the earliest arriving one among fitting standard parcels.
  6. A new container is started when the current one cannot accommodate any remaining priority or standard parcels, or when all available parcels have been processed.
  7. Return a list of lists, where each inner list represents a loaded container and contains the parcelIds of parcels placed into it.

Input & Output

The function signature will be: function loadContainers(parcels: Parcel[], maxWeightCapacity: number): number[][]

  • parcels: An array of Parcel objects. Each Parcel object has the following structure:

    interface Parcel {
        parcelId: number;
        weight: number;
        isPriority: boolean;
    }
    
    • parcelId: A unique numeric identifier for the parcel.
    • weight: The weight of the parcel in units.
    • isPriority: A boolean indicating if the parcel is a priority shipment.
  • maxWeightCapacity: A number representing the maximum total weight a single container can hold.

  • Returns: number[][] - A list of arrays. Each inner array represents a container and contains the parcelIds of the parcels loaded into it. The order of parcelIds within an inner array does not matter, but the order of inner arrays (containers) should reflect the sequence in which they were filled.

Clarifications

  • Parcels arrive in the exact order they are provided in the input parcels array.
  • A container's total loaded weight must never exceed maxWeightCapacity.
  • If the input parcels array is empty, the function should return an empty list [].
  • All parcel weights and maxWeightCapacity will be positive integers.

Examples

1

Example 1

Input:

parcels = [{"parcelId":1,"weight":10,"isPriority":false},{"parcelId":2,"weight":5,"isPriority":true},{"parcelId":3,"weight":12,"isPriority":false}], maxWeightCapacity = 20

Output:

[[2,1],[3]]

Note:

  1. Parcels are initially separated: priorityWaiting = [P2 (5)], standardWaiting = [P1 (10), P3 (12)].
  2. Container 1 (capacity 20):
    • Current weight: 0. Remaining capacity: 20.
    • Attempt to load priority parcels: P2 (5kg) fits. Load P2. currentWeight = 5. Container: [2]. priorityWaiting = [].
    • Remaining capacity: 15. No more priority parcels.
    • Attempt to load standard parcels: P1 (10kg) fits. Load P1. currentWeight = 15. Container: [2, 1]. standardWaiting = [P3 (12)].
    • Remaining capacity: 5. Re-attempt standard parcels: P3 (12kg) does not fit (12 > 5).
    • Container 1 is finalized: [2, 1].
  3. Container 2 (capacity 20):
    • Current weight: 0. Remaining capacity: 20.
    • No priority parcels.
    • Attempt to load standard parcels: P3 (12kg) fits. Load P3. currentWeight = 12. Container: [3]. standardWaiting = [].
    • Container 2 is finalized: [3].
  4. All parcels loaded. Result: [[2, 1], [3]].
2

Example 2

Input:

parcels = [{"parcelId":101,"weight":30,"isPriority":true},{"parcelId":102,"weight":25,"isPriority":true},{"parcelId":103,"weight":15,"isPriority":true}], maxWeightCapacity = 50

Output:

[[101,103],[102]]

Note:

  1. Parcels are initially separated: priorityWaiting = [P101 (30), P102 (25), P103 (15)], standardWaiting = [].
  2. Container 1 (capacity 50):
    • Current weight: 0. Remaining capacity: 50.
    • Attempt to load priority parcels:
      • P101 (30kg) fits. Load P101. currentWeight = 30. Container: [101]. priorityWaiting = [P102 (25), P103 (15)].
      • Remaining capacity: 20. Re-attempt priority parcels:
        • P102 (25kg) does not fit (25 > 20).
        • P103 (15kg) fits. Load P103. currentWeight = 45. Container: [101, 103]. priorityWaiting = [P102 (25)].
      • Remaining capacity: 5. Re-attempt priority parcels:
        • P102 (25kg) does not fit (25 > 5).
    • No more priority parcels fit. Attempt to load standard parcels: standardWaiting is empty.
    • Container 1 is finalized: [101, 103].
  3. Container 2 (capacity 50):
    • Current weight: 0. Remaining capacity: 50.
    • Attempt to load priority parcels:
      • P102 (25kg) fits. Load P102. currentWeight = 25. Container: [102]. priorityWaiting = [].
    • No more priority parcels. Attempt to load standard parcels: standardWaiting is empty.
    • Container 2 is finalized: [102].
  4. All parcels loaded. Result: [[101, 103], [102]].
3

Example 3

Input:

parcels = [], maxWeightCapacity = 100

Output:

[]

Note:

No parcels are provided in the input, so no containers are loaded.

Constraints

Constraints & assumptions

  • 1 <= parcels.length <= 2000
  • 1 <= parcel.weight <= maxWeightCapacity (A single parcel will not exceed container capacity).
  • 1 <= maxWeightCapacity <= 5000
  • parcelId will be unique positive integers.
  • All input values are valid integers.

Out of scope

  • Optimizing for the absolute minimum number of containers. The problem focuses on a specific loading strategy (priority first, then standard, respecting arrival order within groups).
  • Real-time parcel arrival simulation; assume all parcels are available for processing at the start.

What interviewers evaluate

  • Correctness: The solution accurately loads parcels into containers, respecting priority rules and weight constraints.
  • Data Structures: Effective and appropriate use of array-based data structures to manage priority and standard parcels awaiting loading.
  • Algorithmic Efficiency: The solution processes parcels and fills containers efficiently within the given constraints.
  • Code Clarity & Maintainability: The code is well-structured, readable, and easy to understand, reflecting good software engineering practices.

Loading editor...