(Leetcode) 253 - Meeting Room ii 풀이 (Meeting Schedule ii)
기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.
- 문제
내가 작성한 풀이
지난번에 풀었던 meeting room 문제의 심화버전이다. 해당 문제에서 사용했던 풀이를 재활용하였다.
먼저 intervals를 정렬한다. 이후 반복문을 통해 interval을 추가해나가는데, 만약 겹치는 시간대가 있을 경우 새로운 날짜를 생성한다.
public class Solution {
public int minMeetingRooms(List<Interval> intervals) {
intervals = intervals.stream().sorted(Comparator.comparingInt(o -> o.start)).toList();
List<List<Interval>> days = new ArrayList<>();
for(Interval interval : intervals) {
boolean added = false;
for (List<Interval> day : days) {
day.add(interval);
if (canAttendMeetings(day)) {
added = true;
break;
}
day.remove(day.size() - 1);
}
if (!added) {
List<Interval> newDay = new ArrayList<>();
newDay.add(interval);
days.add(newDay);
}
}
return days.size();
}
public boolean canAttendMeetings(List<Interval> intervals) {
for (int i = 0; i < intervals.size() - 1; i++) {
if(intervals.get(i).end > intervals.get(i+1).start) {
return false;
}
}
return true;
}
}
class Interval {
public int start, end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
@Override
public String toString() {
return "{" + start + ", " + end + "}";
}
}
TC, SC
days의 길이를 m 이라고 했을 때, 시간 복잡도는 O(n^2 * m) 공간 복잡도는 O(n) 이다. m 은 최악의 경우 n 이 될 수 있다.