Find right interval

Array Binary Search Sorting

55.4% acceptance

Jan 13, 2026

2352

396

You are given an array of intervals, where intervals[i] = [starti, endi] and each starti is unique. The right interval for an interval i is an interval j such that startj >= endi and startj is minimized. Note that i may equal j. Return an array of right interval indices for each interval i. If no right interval exists for interval i, then put -1 at index i.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn find_right_interval(intervals: Vec<Vec<i32>>) -> Vec<i32> {
    let mut starts: Vec<(i32, usize)> = intervals.iter()
      .enumerate()
      .map(|(i, interval)| (interval[0], i))
      .collect();
    
    starts.sort_by_key(|&(start, _)| start);
    
    intervals.iter().map(|interval| {
      let end = interval[1];
      match starts.binary_search_by_key(&end, |&(start, _)| start) {
        Ok(idx) => starts[idx].1 as i32,
        Err(idx) => {
          if idx < starts.len() {
            starts[idx].1 as i32
          } else {
            -1
          }
        }
      }
    }).collect()
  }
}