LeetCode (통합 구간)

7553 단어 데이터 구조
20200405
제목: 병합 구간
한 구간 의 집합 을 보 여 줍 니 다. 겹 치 는 모든 구간 을 합 쳐 주 십시오.
예시:
  : [[1,3],[2,6],[8,10],[15,18]]
  : [[1,6],[8,10],[15,18]]
  :    [1,3]   [2,6]   ,        [1,6].

생각:
1. 먼저 2 차원 배열 에서 각 1 차원 배열 의 [0] 에 따라 오름차 순 서 를 매 긴 다. 즉, start 에 따라 순 서 를 매 긴 다.2. 합병 조건 은 앞의 끝 이 뒤의 시작 보다 크다 는 것 이다. 그 다음 에 linkedList 를 중간 처리 대상 으로 하고 집합 이 비어 있 거나 조건 을 만족 시 키 지 않 으 면 집합 의 끝 에 가입 한다.4. 집합 이 비어 있 지 않 고 합병 조건 을 만족 시 킬 때 집합 중의 마지막 요 소 를 취하 여 원 치 와 합병 구간 end 의 최대 치 로 하여 금 이러한 구간 문 제 를 해결 하도록 한다.5. 집합 처리 완료, 첫 번 째 요 소 를 반복 해서 end 결과 배열 에 넣 기
code
class Solution{
    public int[][] merge(int[][] arr){
        Arrays.parallelSort(arr,Comparator.comparingInt(x -> x[0]));
        
        LinkedList<int[]> list = new LinkedList<>();
        for(int i=0;i<arr.length;i++){
            if(list.size()==0||list.getLast()[1]<arr[i][0]){
                list.add(arr[i]);
            }else{
                list.getLast()[1] = Math.max(list.getLast()[1],arr[i][1]);
            }
        }
        int[][] res = new int[list.size()][2];
        int index = 0;
        while(!list.isEmpty()){
            res[index++] = list.removeFirst();
        }
        return res;
    }
}

좋은 웹페이지 즐겨찾기