Interval 문제
두 Interval중 겹치는(Overlap) 시간계산은 아래와 같이 계산 할 수 있다. 공식처럼 필요할때 사용할 수 있을듯! 만약 결과가 양수이면 겹치는 시간이 있다는 뜻. 음수이면 겹치지 않는다는 뜻
- A와 B에서
종료시간중 더 작은값-시작 시간 중 더 큰값
가령 현재 A가 [10,50] 이고 B가 [0,15] 일때. 겹치는 시간을 계산하면min(50,15) - max(10,0) => 5가 된다.
Interval 문제는 A가 B보다 시작시간이 빠른경우 아래와 같이 3종류의 겹치는 경우의수가 존재한다.
A 5-----10
B 7------15 (overlap 10-7 = 3)
A 5---------15
B 7---9 (overlap 9-7 = 2)
A 5----9
B 11----15 (overlap 9-11 = -3) 음수!
435. Non-overlapping Intervals
문제
interval이 주어졌을때, 중첩이 발생하지 않도록 interval을 제거할때, 최소한으로 제거할 수 있는 갯수는?
Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.아이디어
- Gready
두 interval이 가질 수 있는 세가지 경우의 수에 따라 각각 처리. Gready하게 O(n)에 계산이 가능해짐. 현재가 cur이고 그 다음 인터벌이 next 라고 할때, 아래와 같이 처리하면 된다. (해설 참고함)
case 1
---- ---
cur next
case 2 : cur을 제거
cur --------x
next ---
case 3 : next를 제거
cur -----
next ------x해결
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
int cur = 0;
int next = 1;
int min_rm = 0;
if (intervals.size() == 1)
return min_rm;
sort(intervals.begin(), intervals.end());
while (next < intervals.size()) {
// if case 1
if (intervals[cur][1] <= intervals[next][0]) {
cur = next; // <- cur will be next , not cur++
next++;
} else if (intervals[cur][1] >= intervals[next][1]) { // case 2
min_rm++;
cur = next; // <- cur will be next
next++;
} else { // case 3
min_rm++;
next++;
}
}
return min_rm;
}
};Pramp - Time Planner
문제
[시작,종료]로 구성된 시작시간으로 정렬된 두명의 빈 가용시간 테이블이 주어진다. 주어진 dur 시간 만큼의 미팅을 하고자할때 현재 두 타임테이블에서 그것이 가능하다면 첫번째로 가능한 예약 시간을 리턴하라.
input: slotsA = [[10, 50], [60, 120], [140, 210]]
slotsB = [[0, 15], [60, 70]]
dur = 8
output: [60, 68]
input: slotsA = [[10, 50], [60, 120], [140, 210]]
slotsB = [[0, 15], [60, 70]]
dur = 12
output: [] # since there is no common slot whose duration is 12해결 아이디어
i
slotsA = [[10, 50], [60, 120], [140, 210]]
j
slotsB = [[0, 15], [60, 70]]-
두 Interval중 겹치는(Overlap) 시간계산은 아래와 같이 계산 할 수 있다. 공식처럼 필요할때 사용할 수 있을듯! 만약 답이 양수이면 겹치는 시간이 있다는 뜻.
- A와 B에서
종료시간중 더 작은값-시작 시간 중 더 큰값
가령 현재 A가 [10,50] 이고 B가 [0,15] 일때. 겹치는 시간을 계산하면min(50,15) - max(10,0) => 5가 된다.
- A와 B에서
-
따라서 이 overlap시간이
dur시간보다 크다면 예약이 가능하다. -
비교할 대상은 two pointer를 활용해서 i, j를 비교한다. 문제는 어떤조건에 i와 j를 증가시킬지이다.
매 루프마다 종료값을 비교했을때 더 작은 요소의 인덱스를 증가시킨다. 아래 예에서 같이 종료 값이 작은 요소B의 다음 요소가 A와 Overlap될 가능성이 있기에 B를 증가시켜서 확인한다. 그래야 모든 interval을 빠짐없이 확인 할수 있다.
i
A -------
j j+1
B ----- ------ (j+1) 과 i 가 Overlap될 수 있음해결 O(m+n)
vector<int> meetingPlanner( const vector<vector<int>>& slotsA, const vector<vector<int>>& slotsB, int dur) {
int i = 0, j = 0;
int min_end = 0, max_begin = 0;
vector<int> ret;
while (i < slotsA.size() && j < slotsB.size()) {
// check with i,j
min_end = min(slotsA[i][1], slotsB[j][1]);
max_begin = max(slotsA[i][0], slotsB[j][0]);
if (min_end - max_begin >= dur) {
ret.push_back(max_begin);
ret.push_back(max_begin + dur);
}
// moving two pointer
if (slotsA[i][1] > slotsB[j][1])
j++;
else
i++;
}
return ret;
}
int main() {
return 0;
}56. Merge Intervals
문제
intervals[i] = [starti, endi] 로 interval이 주어진다. 겹치는 부분을 합쳐라. (참고로 interval[]는 정렬되어있지 않음)
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].해결 O(n)
greedy한 방식으로 첫번째 값과 interval을 비교하면서 겹치면 확장. 안겹치면 push하고 그 값과 다음 interval을 비교한다.
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> ret;
int ret_pos = 0;
std::sort(intervals.begin(), intervals.end());
ret.push_back(intervals[0]);
for (int i = 1; i < intervals.size(); i++) {
if (ret[ret_pos][1] >= intervals[i][0]) {
ret[ret_pos][1] = std::max(ret[ret_pos][1], intervals[i][1]);
} else {
ret.push_back(intervals[i]);
ret_pos++;
}
}
return ret;
}
};57. Insert Interval
문제
서로 겹치지 않는 [시작, 종료] interval 들이 담긴 배열이 주어진다. 새로운 interval이 들어왔을때, 중첩되는 interval을 합쳐서 배열을 다시 구성해라.
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].해결
중첩이 발생하기 전, 그리고 발행 이후는 순서대로 push하고, 중첩부분에서 시작 값중 가장 작은 값과 종료값중 가장 큰값을 push하면 된다.
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
int isize = intervals.size();
vector<vector<int>> ret;
int remains;
vector<int> tmp(2,0);
tmp[0] = newInterval[0];
tmp[1] = newInterval[1];
for (int i = 0; i < isize; i++) {
if (intervals[i][1] < newInterval[0]) {
ret.push_back(intervals[i]);
} else if (newInterval[1] < intervals[i][0]) {
remains = i;
break;
} else {
tmp[0] = std::min(intervals[i][0], tmp[0]);
tmp[1] = std::max(intervals[i][1], tmp[1]);
}
}
ret.push_back(tmp);
for (int i = remains; i < isize; i++)
ret.push_back(intervals[i]);
return ret;
}
};729. My Calendar I
문제
구현문제, [start, end] 시간 예약 함수 book()이 호출될때, 이전 시간과 겹쳐서 예약이 불가능하면 false, 가능하면 true를 리턴하라.
Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]해결
밸런스 트리로 구성되어있는 map자료구조 사용.
- upper_bound(n): n보다 큰 값중에 첫번째 iter
- lower_bound(n): n보다 큰거나 같은 값중에 첫번째 iter
it->second it->first
(5)-----(10) (12)-------(19) (22)-------(24)
(16)-------------(23)
start end우선 end값을 기준으로 정렬한다. map<end, start> 순서 주의.
그리고 새로 들어온 값의 start를 기준으로 upper_bound(start)를 하면 기존 비교해야할 요소의 iterator가 리턴된다.
가령 위와같이 사전에 시간이 예약되어있을때, 새로운 예약 [16,23]이 들어온다고 해보자. upper_bound(16)을 하면 map의 19 요소가 선택될것이다. 만약 end 값이 기존예약 시작지점인 it->second (12) 보다 작다면 예약은 성공한다.
그런데 만약 새로운 값이 [8,11] 이라면? 위의 조건을 만족하지만 false이어야 한다. 하지만 이 경우 upper_bound(5) 는 [5,10]을 리턴하므로 거기서 다시 계산을 하면 된다. 생각하기 어려웠던 문제였다.
class MyCalendar {
map<int, int> cal;
public:
MyCalendar() {
cal.clear();
}
bool book(int start, int end) {
auto it = cal.upper_bound(start);
if (it == cal.end() || end <= it->second)
cal[end] = start;
else
return false;
return true;
}
};
/**
* Your MyCalendar object will be instantiated and called as such:
* MyCalendar* obj = new MyCalendar();
* bool param_1 = obj->book(start,end);
*/252. Meeting Rooms
문제
주어진 배열에는 미팅시간(시작,종료) 리스트가 담겨있다. 한 사람이 모든 미팅에 참여할수 있는지 판단하라.
Input: intervals = [[0,30],[5,10],[15,20]]
Output: falsehttps://leetcode.com/problems/meeting-rooms/
해결 아이디어
- brute force
미팅 시간의 최대범위까지(1000001) 배열을 만들고 각 미팅시간을 표시한다. 미팅 시간을 하나씩 순회하며 이전에 표시가된 배열값을 만나면 false 리턴. - sorting
미팅 시간을 시작시간 기준으로 정렬한다. 그 위 미팅시간을 순서대로 순회하면서 중첩이 되는 부분을 만나면 false시키면 된다.
해결 1 - brute force
#define MAX_TIME 1000001
int timeline[MAX_TIME];
bool canAttendMeetings(int** intervals, int intervalsSize, int* intervalsColSize){
memset(timeline, 0, sizeof(int) * MAX_TIME);
for (int i = 0; i < intervalsSize; i++) {
for (int j = intervals[i][0]; j < intervals[i][1]; j++) {
if (timeline[j] != 0)
return false;
timeline[j]++;
}
}
return true;
}해결 2 - O(NlogN)
추가로 2차원배열을 qsort로 정렬하는 방법 참고하기.
인자로 전달된 값을 우선 (int **)로 형변환 해야함.
int cmp(const void *a, const void *b)
{
int *aval = *(int **)a;
int *bval = *(int **)b;
return aval[0] - bval[0];
}
bool canAttendMeetings(int** intervals, int intervalsSize, int* intervalsColSize){
qsort(intervals, intervalsSize, sizeof(int *), cmp);
for (int i = 0; i < intervalsSize - 1; i++)
if (intervals[i][1] > intervals[i + 1][0])
return false;
return true;
}253. Meeting Rooms II
문제
미팅룸 예약 시간이 담긴 배열이 주어질때, 모든 미팅을 수용할 수 있도록 필요한 최소 미팅룸 갯수를 구하라.[시작시간, 종료시간]
Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2https://leetcode.com/problems/meeting-rooms-ii/
해결 O(NlogN)
먼저 시작시간 기준으로 예약을 정렬한다. 그 뒤 다이어그램을 그려보면 순서대로 시작시간을 만나면 방갯수 +1, 종료시간을 만나면 -1을 하고 최대값을 저장해놓으면 그게 해답이 된다.
가령 예약시간이 [[0,30],[5,10],[15,20]] 으로 정렬되어있을때, 시작, 종료를 순차적으로 정렬해서 나열하면 아래와 같다. (괄호)가 시작시간, 아니면 종료시간.
(0) (5) 10 (15) 20 30
1 2 1 2 1 0그리고 미팅룸 갯수를 순차적으로 계산하면 최대값이 2가 된다.
여러가지 솔루션으로 해결이 가능해서 코딩테스트 문제로 딱 좋을만한 문제인듯!
#define max(a,b) (((a) > (b)) ? (a) : (b))
int cmp(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}
int minMeetingRooms(int** intervals, int intervalsSize, int* intervalsColSize)
{
int *start = (int *)calloc(intervalsSize, sizeof(int));
int *finish = (int *)calloc(intervalsSize, sizeof(int));
for (int i = 0; i < intervalsSize; i++) {
start[i] = intervals[i][0];
finish[i] = intervals[i][1];
}
qsort(start, intervalsSize, sizeof(int), cmp);
qsort(finish, intervalsSize, sizeof(int), cmp);
int ret = 0;
int max_room = 0;
int st_i = 0;
int fi_i = 0;
while (st_i < intervalsSize && fi_i < intervalsSize) {
if (start[st_i] == finish[fi_i]) {
st_i++;
fi_i++;
} else if (st_i < intervalsSize && (start[st_i] < finish[fi_i] || fi_i == intervalsSize)) {
ret++;
st_i++;
max_room = max(ret, max_room);
} else if (fi_i < intervalsSize && (finish[fi_i] < start[st_i] || st_i == intervalsSize)) {
ret--;
fi_i++;
max_room = max(ret, max_room);
}
}
return max_room;
}