n0056_merge_intervals.rs

/**
 * [56] Merge Intervals
 *
 * Given a collection of intervals, merge all overlapping intervals.
 * 
 * Example 1:
 * 
 * 
 * Input: [[1,3],[2,6],[8,10],[15,18]]
 * Output: [[1,6],[8,10],[15,18]]
 * Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
 * 
 * 
 * Example 2:
 * 
 * 
 * Input: [[1,4],[4,5]]
 * Output: [[1,5]]
 * Explanation: Intervals [1,4] and [4,5] are considered overlapping.
 * 
 */
pub struct Solution {}

// submission codes start here

// Definition for an interval.
 #[derive(Debug, PartialEq, Eq)]
 pub struct Interval {
   pub start: i32,
   pub end: i32,
 }

 impl Interval {
   #[inline]
   pub fn new(start: i32, end: i32) -> Self {
     Interval {
       start,
       end
     }
   }
 }
impl Solution {
    pub fn merge(intervals: Vec<Interval>) -> Vec<Interval> {
        let mut intervals = intervals;
        intervals.sort_unstable_by_key(|interval| { interval.start });
        let mut result: Vec<Interval> = Vec::new();
        for interval in intervals.into_iter() {
            match result.last_mut() {
                Some(mut last_inter) => {
                    if last_inter.end >= interval.start {
                        last_inter.end = i32::max(last_inter.end, interval.end);
                        continue
                    }
                },
                None => {}
            }
            result.push(interval);
        }
        result
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_56() {
        assert_eq!(
            Solution::merge(vec![Interval::new(1,3),Interval::new(2,6),Interval::new(8,10),Interval::new(15,18)]),
            vec![Interval::new(1,6),Interval::new(8,10),Interval::new(15,18)]
        );
    }
}