[알고리즘문제] 릿코드 Merge Intervals

leetcode.com/problems/merge-intervals/

Merge Intervals - LeetCode

2차원 배열을 intervals를 주고 원소별 범위가 겹치는 것에 대해 범위를 merge시키는 문제임

원소가 2개인 배열 st를 만들어서 intervals의 원소를 검사해 나가며 겹치는 범위를 st[0] ~ st[1]에 각각 저장

범위를 벗어나는 원소를 만나면 answer배열에 push하고 st를 비운 후 st에 새로운 범위를 입력해 나가며 풀엇다

Time complexity  : O(n)

Space complexity : O(n)

impl Solution {
    pub fn merge(mut intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        intervals.sort();
        let mut answer : Vec<Vec<i32>> = Vec::new();
        let mut st = Vec::new();
        st.push(intervals[0][0]);
        st.push(intervals[0][1]);
        
        for i in 1..intervals.len(){
            if st[1] >= intervals[i][0] {
                if intervals[i][1] > st[1]{ st[1] = intervals[i][1]; }                
            }else{
                answer.push(st.to_owned());
                st.clear();
            }
            if st.is_empty(){
                st.push(intervals[i][0]);
                st.push(intervals[i][1]);
            }
        }
        answer.push(st.to_owned());
        answer
    }
}