Earliest Finish Time for Land and Water Rides I solution and explanation
9 more videos on this problem
Earliest Finish Time for Land and Water Rides I and II | Story To Code | Leetcode 3633 & 3635 | MIKcodestorywithMIK · 33:28 · 8K views
Earliest Finish Time for Land and Water Rides I & II | Leetcode - 3633 & 3635Shivam Gupta · 11:37 · 4K views
3633. Earliest Finish Time for Land and Water Rides I | Leetcode Daily - PythonLeetcode Daily · 5:26 · 2K views
3633. Earliest Finish Time for Land and Water Rides I | Leetcode Biweekly Contest 162Break and Build · 13:08 · 1K views
Earliest Finish Time for Land and Water Rides I | LeetCode 3633 | Java Solution | Developer CoderDeveloper Coder · 15:50 · 454 views
Earliest Finish Time for Land and Water Rides I | LeetCode 3633 - Pythonimpoldev · 9:27 · 360 views
3633. Earliest Finish Time for Land and Water Rides I (Leetcode Easy)Programming Live with Larry · 5:25 · 248 views
LeetCode 3633 & 3635 : Earliest Finish Time for Land and Water Rides I & II | O(N*M) to O(N+M)DCode Thought · 25:30 · 221 views
Earliest Finish Time for Land and Water Rides I | LeetCode 3633Streak To Scale · 6:13 · 178 views
Earliest Finish Time for Land and Water Rides I | LeetCode 3633 | Biweekly 162#programming#practicecodemintt · 17:22 · 159 views
The problem
You are given two categories of theme park attractions: land rides and water rides.
- Land rides
landStartTime[i]– the earliest time theithland ride can be boarded.landDuration[i]– how long theithland ride lasts.
- Water rides
waterStartTime[j]– the earliest time thejthwater ride can be boarded.waterDuration[j]– how long thejthwater ride lasts.
A tourist must experience exactly one ride from each category, in either order.
- A ride may be started at its opening time or any later moment.
- If a ride is started at time
t, it finishes at timet + duration. - Immediately after finishing one ride the tourist may board the other (if it is already open) or wait until it opens.
Return the earliest possible time at which the tourist can finish both rides.
Example 1:
Input: landStartTime = [2,8], landDuration = [4,1], waterStartTime = [6], waterDuration = [3]
Output: 9
Explanation:
- Plan A (land ride 0 → water ride 0):
- Start land ride 0 at time
landStartTime[0] = 2. Finish at2 + landDuration[0] = 6. - Water ride 0 opens at time
waterStartTime[0] = 6. Start immediately at6, finish at6 + waterDuration[0] = 9.
- Start land ride 0 at time
- Plan B (water ride 0 → land ride 1):
- Start water ride 0 at time
waterStartTime[0] = 6. Finish at6 + waterDuration[0] = 9. - Land ride 1 opens at
landStartTime[1] = 8. Start at time9, finish at9 + landDuration[1] = 10.
- Start water ride 0 at time
- Plan C (land ride 1 → water ride 0):
- Start land ride 1 at time
landStartTime[1] = 8. Finish at8 + landDuration[1] = 9. - Water ride 0 opened at
waterStartTime[0] = 6. Start at time9, finish at9 + waterDuration[0] = 12.
- Start land ride 1 at time
- Plan D (water ride 0 → land ride 0):
- Start water ride 0 at time
waterStartTime[0] = 6. Finish at6 + waterDuration[0] = 9. - Land ride 0 opened at
landStartTime[0] = 2. Start at time9, finish at9 + landDuration[0] = 13.
- Start water ride 0 at time
Plan A gives the earliest finish time of 9.
Example 2:
Input: landStartTime = [5], landDuration = [3], waterStartTime = [1], waterDuration = [10]
Output: 14
Explanation:
- Plan A (water ride 0 → land ride 0):
- Start water ride 0 at time
waterStartTime[0] = 1. Finish at1 + waterDuration[0] = 11. - Land ride 0 opened at
landStartTime[0] = 5. Start immediately at11and finish at11 + landDuration[0] = 14.
- Start water ride 0 at time
- Plan B (land ride 0 → water ride 0):
- Start land ride 0 at time
landStartTime[0] = 5. Finish at5 + landDuration[0] = 8. - Water ride 0 opened at
waterStartTime[0] = 1. Start immediately at8and finish at8 + waterDuration[0] = 18.
- Start land ride 0 at time
Plan A provides the earliest finish time of 14.
Constraints:
1 <= n, m <= 100landStartTime.length == landDuration.length == nwaterStartTime.length == waterDuration.length == m1 <= landStartTime[i], landDuration[i], waterStartTime[j], waterDuration[j] <= 1000
Approach overview
Problem Overview: You must take exactly one land ride and one water ride. Each ride has an available start time and a duration. After finishing the land ride, you choose a water ride and may need to wait until it becomes available. The goal is to minimize the final completion time.
Approach 1: Brute Force Enumeration (O(n * m) time, O(1) space)
Try every possible pair of land and water rides. For each land ride i, compute when you finish it: finishLand = landStart[i] + landDuration[i]. Then iterate through every water ride j and compute the actual start time startWater = max(finishLand, waterStart[j]). The total completion time becomes startWater + waterDuration[j]. Track the minimum across all pairs. This approach is straightforward and demonstrates the core scheduling logic, but it becomes slow when both ride lists are large.
Approach 2: Enumeration + Greedy with Sorting and Binary Search (O((n + m) log m) time, O(m) space)
Instead of scanning every water ride for each land ride, sort water rides by their start time. For each land ride, compute finishLand and use binary search to find the first water ride whose start time is greater than or equal to this value. That ride lets you start immediately without extra waiting. For water rides that start earlier than finishLand, you can still take them but must wait until the land ride finishes. Precomputing the best candidate (such as minimum duration or minimum finish time) in suffix arrays lets you quickly determine the optimal choice after the binary search. This reduces the repeated scanning and turns the nested loop into a logarithmic lookup.
This method combines simple enumeration of land rides with a greedy choice among water rides. Sorting enables fast lookups, while binary search identifies the earliest feasible candidate. The technique is common in scheduling problems where one event must follow another.
Related concepts appear frequently in problems involving arrays, binary search, and greedy scheduling with sorted events. Two-pointer variants can further optimize scanning when both lists are processed in order.
Recommended for interviews: The enumeration + greedy approach with sorting and binary search is the expected solution. Interviewers often accept brute force as a starting point, but optimizing it with sorted events and fast lookups demonstrates strong problem‑solving and algorithmic thinking.
Solution
We can consider two orders of rides: first land rides then water rides, or first water rides then land rides.
For each order, we first calculate the earliest end time minEnd of the first type of ride, then enumerate the second type of ride and calculate the earliest end time of the second type of ride as max(minEnd, startTime) + duration, where startTime is the start time of the second type of ride. We take the minimum value among all possible earliest end times as the answer.
Finally, we return the minimum value between the answers of the two orders.
The time complexity is O(n + m), where n and m are the numbers of land rides and water rides respectively. The space complexity is O(1).
class Solution:
def earliestFinishTime(self, landStartTime: List[int], landDuration: List[int], waterStartTime: List[int], waterDuration: List[int]) -> int:
def calc(a1, t1, a2, t2):
min_end = min(a + t for a, t in zip(a1, t1))
return min(max(a, min_end) + t for a, t in zip(a2, t2))
x = calc(landStartTime, landDuration, waterStartTime, waterDuration)
y = calc(waterStartTime, waterDuration, landStartTime, landDuration)
return min(x, y)class Solution {
public int earliestFinishTime(
int[] landStartTime, int[] landDuration, int[] waterStartTime, int[] waterDuration) {
int x = calc(landStartTime, landDuration, waterStartTime, waterDuration);
int y = calc(waterStartTime, waterDuration, landStartTime, landDuration);
return Math.min(x, y);
}
private int calc(int[] a1, int[] t1, int[] a2, int[] t2) {
int minEnd = Integer.MAX_VALUE;
for (int i = 0; i < a1.length; ++i) {
minEnd = Math.min(minEnd, a1[i] + t1[i]);
}
int ans = Integer.MAX_VALUE;
for (int i = 0; i < a2.length; ++i) {
ans = Math.min(ans, Math.max(minEnd, a2[i]) + t2[i]);
}
return ans;
}
}class Solution {
public:
int earliestFinishTime(vector<int>& landStartTime, vector<int>& landDuration, vector<int>& waterStartTime, vector<int>& waterDuration) {
int x = calc(landStartTime, landDuration, waterStartTime, waterDuration);
int y = calc(waterStartTime, waterDuration, landStartTime, landDuration);
return min(x, y);
}
int calc(vector<int>& a1, vector<int>& t1, vector<int>& a2, vector<int>& t2) {
int minEnd = INT_MAX;
for (int i = 0; i < a1.size(); ++i) {
minEnd = min(minEnd, a1[i] + t1[i]);
}
int ans = INT_MAX;
for (int i = 0; i < a2.size(); ++i) {
ans = min(ans, max(minEnd, a2[i]) + t2[i]);
}
return ans;
}
};function earliestFinishTime(
landStartTime: number[],
landDuration: number[],
waterStartTime: number[],
waterDuration: number[],
): number {
const x = calc(landStartTime, landDuration, waterStartTime, waterDuration);
const y = calc(waterStartTime, waterDuration, landStartTime, landDuration);
return Math.min(x, y);
}
function calc(a1: number[], t1: number[], a2: number[], t2: number[]): number {
let minEnd = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < a1.length; i++) {
minEnd = Math.min(minEnd, a1[i] + t1[i]);
}
let ans = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < a2.length; i++) {
ans = Math.min(ans, Math.max(minEnd, a2[i]) + t2[i]);
}
return ans;
}func earliestFinishTime(landStartTime []int, landDuration []int, waterStartTime []int, waterDuration []int) int {
x := calc(landStartTime, landDuration, waterStartTime, waterDuration)
y := calc(waterStartTime, waterDuration, landStartTime, landDuration)
return min(x, y)
}
func calc(a1 []int, t1 []int, a2 []int, t2 []int) int {
minEnd := math.MaxInt32
for i := 0; i < len(a1); i++ {
minEnd = min(minEnd, a1[i]+t1[i])
}
ans := math.MaxInt32
for i := 0; i < len(a2); i++ {
ans = min(ans, max(minEnd, a2[i])+t2[i])
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n * m) | O(1) | Small inputs or when first reasoning about the scheduling logic |
| Enumeration + Greedy with Sorting & Binary Search | O((n + m) log m) | O(m) | Preferred approach for interviews and large datasets |
| Two Pointers on Sorted Rides | O(n + m) | O(1) | When both ride lists are processed in sorted order and you scan them simultaneously |
Frequently asked questions
Is Earliest Finish Time for Land and Water Rides I easy or hard?
The problem is classified as Easy. The core idea is straightforward enumeration with scheduling logic, but recognizing the sorting and binary search optimization helps reduce time complexity and demonstrates stronger algorithmic understanding.
Earliest Finish Time for Land and Water Rides I Python/Java solution
Typical implementations enumerate land rides and use binary search over a sorted list of water rides. The logic is identical across Python, Java, C++, Go, and TypeScript: compute the land finish time, locate the best water ride, and update the global minimum completion time.
What is the best approach for Earliest Finish Time for Land and Water Rides I?
The most practical approach is enumeration combined with a greedy selection of water rides after sorting them by start time. For each land ride, compute the finish time and use binary search to locate the earliest compatible water ride. This reduces repeated scanning and achieves about O((n + m) log m) time complexity.
How to solve Earliest Finish Time for Land and Water Rides I in O((n+m) log m)?
Sort the water rides by their start time. For each land ride, compute when it finishes and use binary search to find the first water ride whose start time is at least that finish time. Combine that candidate with precomputed best options to determine the minimum completion time efficiently.
Is Earliest Finish Time for Land and Water Rides I asked at Google/Amazon/Meta?
Problems involving ride scheduling and earliest completion time commonly appear in interviews at companies like Amazon and Google under greedy or interval scheduling categories. Variations test your ability to combine sorting, binary search, and greedy decisions.
What data structure is used in Earliest Finish Time for Land and Water Rides I?
The solution primarily uses arrays along with sorting and binary search. Some implementations maintain auxiliary arrays such as suffix minimums to quickly determine the best water ride candidate after a binary search lookup.
What is the time complexity of Earliest Finish Time for Land and Water Rides I?
The brute force solution runs in O(n * m) because every land ride is paired with every water ride. The optimized method sorts water rides and performs binary search for each land ride, resulting in O((n + m) log m) time with O(m) extra space.
