매일 조금씩

처음에 매우 복잡하게 생각했던 문제다. 그냥 단순히 겹치는 구간이 있는건 하나로 묶인다고 생각하고,총 몇개의 묶음구간이 있는지 구하는 것과 같다.그래서 끝점 기준으로 오름차순 정렬한 후, 현재까지의 겹치는 구간의 끝점을 기억하고 진행하는 것이 포인트다.현재 구간의 시작점이 그 보다 크면 현재 구간부터 새로운 묶음이 시작되어야 한다는 것이다.  추가로, 잊고 있었는데Arrays.sort(arr, (a,b) -> a[1]-b[1]); 를 쓰면 비교대상 값이 음수인 경우 오버플로가 발생할 수 있어서, 안전하게Arrays.sort(arr, (a,b) -> Integer.compare(a[1],b[1]));를 쓰는 것이 좋다. class Solution { public int findMinArrowShots..

이문제는 겹치는 구간을 삭제하는 문제이지만,삭제할 구간의 "최소" 갯수를 구하는 것이 포인트다.무심코 시작점 기준으로 오름차순 정렬 후, 시작점이 같은 경우 끝점의 오름차순으로 정렬하면 안된다..구간의 크기가 큰 구간이 있다면, 그 뒤의 구간들 중 해당 구간의 끝점보다 끝점이 더 작거나 같은 구간들은 싹다 삭제가 될거다..맨처음 구간만 삭제되면 될것을.. 예를 들어,intervals = [[1,5], [2,3], [3,4], [5,6]] 이면 [1,5]만 삭제하면 되는데 시작점 오름차순 정렬 후, 비교하면 [2,3], [3,4]를 삭제해야 하는것으로 나온다.  class Solution { public int eraseOverlapIntervals(int[][] intervals) { ..

간격의 배열이 주어지면, 중복된 부분은 합치면서 최적화된 배열을 리턴하는 문제이다.합치는 과정을 잘하려면 초기에 간격의 시작점을 기준으로 오름차순 정렬을 하고 합치기를 시작해야한다.  class Solution { public int[][] merge(int[][] intervals) { int n = intervals.length; List output = new ArrayList(); // start를 기준으로 오름차순 정렬, // start가 같을 땐, end를 기준으로 오름차순 정렬 Arrays.sort(intervals, (a, b) -> { if (a[0] == b[0]) { ..

새로운 구간이 기존 구간들 중 어디 들어가야할지,어느곳에 들어간다면 기존 구간과 겹치면 어떻게 합쳐져야할지가 중요한 문제다. start를 기준으로 쫙 비교를 해서 새로운 구간보다 start가 빠른 구간들을 결과 배열에 쫙 먼저 넣는다.새로운 구간이 결과 배열의 제일 뒤의 구간과 안겹치면 그냥 제일 뒤에 넣고,겹치면 두 구간의 end 중 큰 구간을 결과 배열의 제일 뒤 구간의 end 값으로 함 (합치기)그리고 나머지 구간들을 마저 넣을 때, 위 과정을 반복하며, 그냥 넣을지 합칠지 한다. class Solution { public int[][] insert(int[][] intervals, int[] newInterval) { int newStart = newInterval[0]; ..