Earliest finish time for land and water rides ii

impl Solution {
  pub fn earliest_finish_time(
    land_start_time: Vec<i32>,
    land_duration: Vec<i32>,
    water_start_time: Vec<i32>,
    water_duration: Vec<i32>,
  ) -> i32 {
    let n = land_start_time.len();
    let m = water_start_time.len();
    // land_end[i] = land_start_time[i] + land_duration[i]
    // water_end[j] = water_start_time[j] + water_duration[j]
    // For land->water: finish = max(land_end[i], water_start_time[j]) + water_duration[j]
    //   = land_end[i] + water_duration[j]  if land_end[i] >= water_start_time[j]
    //   = water_end[j]                       if land_end[i] < water_start_time[j]
    // For water->land: finish = max(water_end[j], land_start_time[i]) + land_duration[i]
    //   = water_end[j] + land_duration[i]   if water_end[j] >= land_start_time[i]
    //   = land_end[i]                        if water_end[j] < land_start_time[i]
    //
    // Sort by land_end and water_start_time for efficient computation.

    // Compute land finishes
    let land_end: Vec<i32> = (0..n).map(|i| land_start_time[i] + land_duration[i]).collect();
    let water_end: Vec<i32> = (0..m).map(|j| water_start_time[j] + water_duration[j]).collect();

    // Sort water by start time for binary search
    let mut water_sorted_by_start: Vec<(i32, i32)> = (0..m).map(|j| (water_start_time[j], water_end[j])).collect();
    water_sorted_by_start.sort_unstable();
    // Prefix max of water_end sorted by start time
    // For land->water: if land_end[i] < water_start[j], finish = water_end[j]
    //   We want to minimize: for all j with water_start[j] > land_end[i], min(water_end[j])
    // For land->water if land_end[i] >= water_start[j], finish = land_end[i] + water_duration[j]
    //   = land_end[i] + (water_end[j] - water_start[j])
    //   We want to minimize water_duration[j] for j with water_start[j] <= land_end[i]
    //   i.e. min(water_end[j] - water_start[j]) for j with water_start[j] <= land_end[i]
    
    let ws_starts: Vec<i32> = water_sorted_by_start.iter().map(|&(s,_)| s).collect();
    let ws_ends: Vec<i32> = water_sorted_by_start.iter().map(|&(_,e)| e).collect();
    let ws_durs: Vec<i32> = water_sorted_by_start.iter().zip(water_end.iter()).map(|(&(s,e), _)| e - s).collect();

    // prefix min duration (water_end - water_start) for water rides with start <= threshold
    let mut prefix_min_dur = vec![i32::MAX; m + 1];
    for j in 0..m {
      prefix_min_dur[j + 1] = prefix_min_dur[j].min(ws_durs[j]);
    }
    // suffix min of water_end for water rides sorted by start
    let mut suffix_min_end = vec![i32::MAX; m + 1];
    for j in (0..m).rev() {
      suffix_min_end[j] = suffix_min_end[j + 1].min(ws_ends[j]);
    }

    // Similarly for water->land
    let mut land_sorted_by_start: Vec<(i32, i32)> = (0..n).map(|i| (land_start_time[i], land_end[i])).collect();
    land_sorted_by_start.sort_unstable();
    let ls_starts: Vec<i32> = land_sorted_by_start.iter().map(|&(s,_)| s).collect();
    let ls_ends: Vec<i32> = land_sorted_by_start.iter().map(|&(_,e)| e).collect();
    let ls_durs: Vec<i32> = land_sorted_by_start.iter().map(|&(s,e)| e - s).collect();

    let mut prefix_min_dur_l = vec![i32::MAX; n + 1];
    for i in 0..n {
      prefix_min_dur_l[i + 1] = prefix_min_dur_l[i].min(ls_durs[i]);
    }
    let mut suffix_min_end_l = vec![i32::MAX; n + 1];
    for i in (0..n).rev() {
      suffix_min_end_l[i] = suffix_min_end_l[i + 1].min(ls_ends[i]);
    }

    let mut best = i32::MAX;

    // For each land ride, find best water pairing
    for i in 0..n {
      let le = land_end[i];
      // Binary search: last water with start <= le
      let pos = ws_starts.partition_point(|&s| s <= le);
      // Case 1: water_start <= land_end => finish = land_end + min_water_dur
      if pos > 0 {
        let min_dur = prefix_min_dur[pos];
        if min_dur < i32::MAX {
          best = best.min(le + min_dur);
        }
      }
      // Case 2: water_start > land_end => finish = min(water_end for those j)
      if pos < m {
        let min_end = suffix_min_end[pos];
        if min_end < i32::MAX {
          best = best.min(min_end);
        }
      }
    }

    // For each water ride, find best land pairing
    for j in 0..m {
      let we = water_end[j];
      let pos = ls_starts.partition_point(|&s| s <= we);
      // Case 1: land_start <= water_end => finish = water_end + min_land_dur
      if pos > 0 {
        let min_dur = prefix_min_dur_l[pos];
        if min_dur < i32::MAX {
          best = best.min(we + min_dur);
        }
      }
      // Case 2: land_start > water_end => finish = min(land_end for those i)
      if pos < n {
        let min_end = suffix_min_end_l[pos];
        if min_end < i32::MAX {
          best = best.min(min_end);
        }
      }
    }

    best
  }
}