Java Sweep Line Algorithm


  • 0
    Y
    /**
     * 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;
            Time[] times = new Time[intervals.length * 2];
            int p = 0;
            for (Interval i : intervals) {
                times[p ++] = new Time(i.start, i);
                times[p ++] = new Time(i.end, i);
            }
            Arrays.sort(times);
            int ans = 0;
            int i = 0;
            int room = 0;
            while (i < times.length) {
                int time = times[i].time;
                int j = i;
                for (; j < times.length && times[j].time == time; j ++) {
                    if (times[j].interval.end == time) room --;
                    else room ++;
                }
                ans = Math.max(ans, room);
                i = j;
            }
            return ans;
        }
    }
    
    class Time implements Comparable<Time> {
        int time;
        Interval interval;
        
        public Time(int t, Interval i) {
            time = t;
            interval = i;
        }
        
        public int compareTo(Time that) {
            if (this.time != that.time) return this.time - that.time;
            else return this.interval.start - that.interval.start;
        }
    }
    

Log in to reply
 

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