Java O(n) sweepline solution


  • 4
    Y

    I used a list of int array to save each start and end point. I used 1 to mark the start and 0 for end, this way end comes before start in case their time equals to each other. For example, [5, 13], [13, 15] will only need one meeting room. So if end comes before start, the meeting room count will decrease by one before increase.

    Then we just iterate the new list, increment count by 1 when see a start and decrement 1 when see a end time. ans will keep the final result. Hope it helps!

    public class Solution {
        public int minMeetingRooms(Interval[] intervals) {
            List<int[]> meet = new ArrayList<>();
            for(Interval interval : intervals) {
                meet.add(new int[] {interval.start, 1});
                meet.add(new int[] {interval.end, 0});
            }
            Collections.sort(meet, new Comparator<int[]> () {
                public int compare(int[] a, int[] b) {
                    return a[0] == b[0] ? a[1] - b[1] : a[0] - b[0];
                }
            });
            int count = 0;
            int ans = 0;
            for(int[] m : meet) {
                if(m[1] == 1) {
                    count++;
                } else {
                    count--;
                }
                ans = Math.max(ans, count);
            }
            return ans;
        }
    }

  • 1

    sort in O(n) time?


  • 0
    F

    The time complexity should be O(nlogn) since you sort the list


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.