253. Meeting Rooms II

Meeting Rooms II

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

For example, Given [[0, 30],[5, 10],[15, 20]], return 2.

Solution

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
      public int minMeetingRooms(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) return 0;
        if (intervals.length == 1) return 1;

        Arrays.sort(intervals, (a, b) -> a.start - b.start);

        List<List<Interval>> lists = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            Interval current = intervals[i];

            int j = 0;
            for (; j < lists.size(); j++) {
                if (conflict(current, lists.get(j))) {
                    continue;
                } else {
                    break;
                }
            }

            if (j != lists.size()) {
                lists.get(j).add(current);
            } else {
                lists.add(new ArrayList<>());
                lists.get(lists.size() - 1).add(current);
            }
        }

        return lists.size();
    }

    private boolean conflict(Interval current, List<Interval> intervals) {
        if (intervals.isEmpty()) {
            return false;
        }

        Interval last = intervals.get(intervals.size() - 1);
        if (last.end > current.start || current.start == last.start) {
            return true;
        } else {
            return false;
        }
    }
}