Be the first user to complete this post

  • 0
 Add to List
Hard

501. Valid Pickup and Delivery options

Given N orders, each order consists of pickup and delivery services, means delivery of a particular service will after the pick up of the same service so the sequence pickup/delivery such that delivery(i) is after pickup(i).

Write a program to count all valid pickup/delivery possible sequences

Since the answer may be too large, return it modulo 10^9 + 7.

Example: 

Input: N = 1
Output: 1
Note: (P1, D1), Delivery 1 always is after of Pickup

Input: N = 2
Output: 6
Explanation: All possible orders: 
(P1,P2,D1,D2), (P1,P2,D2,D1), (P1,D1,P2,D2), (P2,P1,D1,D2), (P2,P1,D2,D1) and (P2,D2,P1,D1).
This is an invalid order (P1, D2, P2, D1) because Pickup 2 is after Delivery 2.

Input: N = 3
Output: 90

Approach:

Find all permutations:

Let's say there are N = 2 orders which means there are two pickups P1, P2 and 2 delivery D1, D2.Lets consider each as an individual event which needs to take place. Permutation of these events happening is !4 = 4x3x2x1 = 24(you have 4 options to pick for the first event, 3 options when picking second option, 2 options for third and only one option for the last one. 

Filter out the invalid ones:

Now in this 24 sequences we have picked the invalid ones as well like (P1, D2, P2, D1) or (D1, D2, P2, P1). So for each order (P1, D1) is valid and (D1, P1) is invalid. So for each pair we need to divide the permutation by 2 to remove the invalid ones. So for N = 2, we need to divide by 2x2. So our answer would be 24/4 = 6. 

So for any N, the final result would be !2N/2N. Keep taking Mod with 10^9 + 7 before the answer gets large.

Time Complexity: O(N)

Output: 

N = 2, Valid pickup/delivery pairs: 6
N = 3, Valid pickup/delivery pairs: 90
N = 7, Valid pickup/delivery pairs: 681080400

Reference: Leetcode

Related Problems: