impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let (mut left, mut right) = (0, nums.len());
        while left < right {
            let mid = left + (right - left) / 2;
            if nums[mid] == target {
                return mid as i32;
            } else if nums[mid] < target {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return -1;
    }
}

impl Solution {
    pub fn min_window(s: String, t: String) -> String {
        let (m, n, mut start, mut min_len) = (s.len(), t.len(), -1, std::i32::MAX);
        let mut dp : Vec<Vec<i32>> = vec![vec![-1; n + 1]; m + 1];
        for i in 0..m + 1 {
            dp[i][0] = i as i32;
        }
        for i in 1..m + 1 {
            for j in 1..std::cmp::min(i, n) + 1 {
                if s.chars().nth(i - 1).unwrap() == t.chars().nth(j - 1).unwrap() {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }

            if dp[i][n] != -1 {
                let len = i - dp[i][n] as usize;
                if min_len as usize > len {
                    min_len = len as i32;
                    start = dp[i][n];
                }
            }
        }

        if start != -1 {
            let slice = &s[start as usize..(start + min_len) as usize];
            return (slice.to_string().clone()).parse().unwrap();
        } else {
            return "".to_string();
        }
    }
}

struct MyCalendar {
    events: Vec<Vec<i32>>
}


/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl MyCalendar {

    fn new() -> Self {
        MyCalendar {
            events: vec![]
        }
    }

    fn book(&mut self, start: i32, end: i32) -> bool {
        if self.events.len() == 0 {
            self.events.push(vec![start, end]);
            return true;
        }
        
        for e in &self.events {
            let (ss, ee) = (e[0], e[1]);
            if start < ee && end > ss {
                return false;
            }
        }

        self.events.push(vec![start, end]);
        return true;
    }
}

/**
 * Your MyCalendar object will be instantiated and called as such:
 * let obj = MyCalendar::new();
 * let ret_1: bool = obj.book(start, end);
 */