Asked in: UBER
Image of the Question
All Testcases Passed ✔
Solution
def maximiZeDropDelay(scheduleDrop, realDrop):
ans = 0
scheduleDrop.sort()
realDrop.sort(reverse = True)
// ... rest of solution available after purchaseExplanation
```
To approach this problem, let's carefully analyze what is being asked and what variables we can control to maximize the weighted drop delay.
The key formula to maximize is:
Total Weighted Drop Delay = ∑ i * (realDrop[i] - scheduledDrop[i]) for i from 1 to n.
Here, i is the zone number (1-based index), realDrop[i] is the actual drop time assigned to zone i, and scheduledDrop[i] is the scheduled drop time assigned to zone i.
Important points to note:
- We are allowed to reorder both scheduledDrop and realDrop arrays independently before pairing them by index to calculate the weighted drop delay.
- Our goal is to maximize the sum of weighted differences multiplied by their zone indices.
- Because the arrays are large (up to 10^5 elements), an efficient approach is needed.
- The answer must be modulo 10^9+7 due to potentially large values.
---
**Step 1: Understanding the Problem Intuitively**
We want to pair elements from the scheduledDrop and realDrop arrays to maximize the sum:
∑ i * (realDrop[i] - scheduledDrop[i]).
Since i is fixed by the final order of the arrays after rearrangement, and we are free to permute scheduledDrop and realDrop independently, the problem boils down to how to pair elements optimally.
Rewrite the sum as:
∑ i * realDrop[i] - ∑ i * scheduledDrop[i].
The terms i * realDrop[i] and i * scheduledDrop[i] depend on how we assign values to indices i.
Our freedom:
- We can reorder scheduledDrop arbitrarily.
- We can reorder realDrop arbitrarily.
Our goal is to find permutations of scheduledDrop and realDrop that maximize the difference of weighted sums:
(∑ i * realDrop[i]) - (∑ i * scheduledDrop[i]).
---
**Step 2: Applying Rearrangement Inequality**
This is a classic scenario for applying the rearrangement inequality, which states that to maximize the sum of products of two sequences, both sequences should be sorted in the same order (both ascending or both descending). To minimize the sum of products, one should sort one sequence ascending and the other descending.
In our problem, we want to maximize:
∑ i * realDrop[i] - ∑ i * scheduledDrop[i] = (∑ i * realDrop[i]) - (∑ i * scheduledDrop[i]).
Since i is fixed (1 to n in order), we can think about how to assign the scheduledDrop and realDrop values to indices i optimally.
Note: We do not reorder i, only the arrays scheduledDrop and realDrop.
Imagine sequences:
- weights = [1, 2, 3, ..., n] (fixed ascending order)
- scheduledDrop: we want to assign to positions to minimize ∑ i * scheduledDrop[i] to maximize the total difference.
- realDrop: we want to assign to positions to maximize ∑ i * realDrop[i].
Therefore:
- Assign the smallest scheduledDrop values to the largest weights (positions with large i) to minimize ∑ i * scheduledDrop[i].
- Assign the largest realDrop values to the largest weights to maximize ∑ i * realDrop[i].
---
**Step 3: Determining the Ordering**
So, for maximum weighted drop delay:
- Sort scheduledDrop in ascending order and assign them to positions in descending order of i (largest i gets smallest scheduledDrop).
- Sort realDrop in ascending order and assign them to positions in ascending order of i (largest i gets largest realDrop).
Or equivalently:
- For scheduledDrop, assign the smallest values to the largest weights (positions with large i).
- For realDrop, assign the largest values to the largest weights.
Hence, the final pairing is:
- scheduledDrop sorted ascending → assigned to positions with i descending (index n, n-1, ..., 1).
- realDrop sorted ascending → assigned to positions with i ascending (index 1, 2, ..., n).
This setup ensures the difference ∑ i * (realDrop[i] - scheduledDrop[i]) is maximized.
---
**Step 4: Calculating the Result**
After sorting and rearranging arrays as per above:
- For each position i, calculate difference = realDrop[i] - scheduledDrop[i].
- Multiply difference by i (the position index).
- Sum all such terms for i from 1 to n.
Finally, take the result modulo (10^9 + 7) before returning.
---
**Step 5: Edge Cases and Validation**
- Arrays might contain very large values, so use 64-bit integers for intermediate computations to avoid overflow before modulo.
- Confirm that both arrays have the same length n.
- Handle modulo only at the final sum to prevent affecting intermediate computations unnecessarily.
---
**Summary**
To solve the problem:
- Sort scheduledDrop in ascending order.
- Sort realDrop in ascending order.
- Assign scheduledDrop smallest elements to highest i positions (reverse the sorted scheduledDrop).
- Assign realDrop in ascending order to i in ascending order.
- Compute the sum ∑ i * (realDrop[i] - scheduledDrop[i]) modulo 10^9+7.
- Return the computed sum.
This approach leverages the rearrangement inequality to pair elements optimally, ensuring the weighted drop delay is maximized.
```