궁금한게 많은 개발자 노트

start를 기준으로 오름차순으로 정렬된 겹치지 않는 구간 리스트가 주어졌을 때, 한 구간을 리스트에 삽입하는 문제입니다. 만약 삽입하는 과정에서 겹치는 구간이 발생하면 병합하여 하나의 구간을 만들어야 합니다. Binary Search로 삽입할 index를 구하고, 해당 index를 기준으로 좌우로 two pointer로 넓혀가며 겹치는 구간을 찾고, 겹치는 구간이 있다면 삭제 후 병합한 새 구간을 넣어서 해결하였습니다. #include class Solution { public: vector insert(vector& intervals, vector& newInterval) { vector::iterator insert_index = upper_bound(intervals.begin(), interva..

여러 구간들이 주어졌을 때, 어떤 한 구간이 다른 구간에 포함되는 경우 제거하고 남은 구간의 수를 반환하는 문제입니다. 이 때 정렬이 필요한데, 기본 오름 차순 정렬이 아닌 start는 오름 차순이고 end는 큰수가 먼저 앞에 오도록 정렬해야 순서대로 확인 시 다음 구간을 포함하는지 확인하기에 용이합니다. #include bool compare(vector a, vector b) { if (a[0] == b[0]) return a[1] > b[1]; return a[0] < b[0]; } class Solution { public: int removeCoveredIntervals(vector& intervals) { sort(intervals.begin(), intervals.end(), compare)..

여러 구간들이 주어졌을 때, 겹치는 구간을 병합하여 겹치지 않는 구간들의 리스트를 반환하는 문제입니다. 먼저 구간들을 오름차순으로 정렬하고, 정답 리스트에 구간을 하나 추가하고 마지막 추가된 구간과 새로 들어갈 구간들이 겹치는지 판단하여 겹치는 경우 마지막 구간을 빼서 병합하고 다시 넣어주는 과정을 반복합니다. #include #define max(a,b)((a) > (b) ? (a) : (b)) class Solution { public: vector merge(vector& intervals) { sort(intervals.begin(), intervals.end()); vector answer; for (int i = 0; i < intervals.size(); i++) { int start = i..