[그라인드 75] 57. 간격 삽입
설명
겹치지 않는 간격 배열intervals이 제공됩니다. 여기서 intervals[i] = [starti, endi]는 ith 간격의 시작과 끝을 나타내고 intervals는 starti에 의해 오름차순으로 정렬됩니다. 또한 다른 간격의 시작과 끝을 나타내는 간격newInterval = [start, end]도 제공됩니다.
newInterval가 intervals에 의해 오름차순으로 정렬되고 intervals에 여전히 겹치는 간격이 없도록 starti를 intervals에 삽입합니다(필요한 경우 겹치는 간격 병합).
삽입 후 반환intervals
예 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
예 2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
제약:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
0 <= intervals.length <= 104 intervals[i].length == 2 0 <= starti <= endi <= 105 intervals는 starti를 기준으로 오름차순으로 정렬됩니다. newInterval.length == 2 0 <= start <= end <= 105 솔루션
솔루션 1
직관
end < newStart 암호
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
int n = intervals.size();
vector<vector<int>> res;
int idx = 0;
while (idx < n && intervals[idx][1] < newInterval[0]) res.push_back(intervals[idx++]);
if (idx < n) {
newInterval[0] = min(intervals[idx][0], newInterval[0]);
while (idx < n && intervals[idx][0] <= newInterval[1])
newInterval[1] = max(intervals[idx++][1], newInterval[1]);
}
res.push_back(newInterval);
while (idx < n) res.push_back(intervals[idx++]);
return res;
}
};
복잡성
Reference
이 문제에 관하여([그라인드 75] 57. 간격 삽입), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/jiangwenqi/grind-75-57-insert-interval-4kp8텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
