Java Solution follows Simple Greedy Algorithm in Book Algorithm Design --- for understanding simple greedy approach


  • 0
    /**
     * 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 {
        // Each room has a schedule
        public class Schedule {
            int end;
            Schedule(int end) {
                this.end = end;
            }
        }
        public int minMeetingRooms(Interval[] intervals) {
            if (intervals == null || intervals.length == 0) return 0;
            // Sort intervals by start time
            Arrays.sort(intervals, new Comparator<Interval>() {
                public int compare(Interval a, Interval b) {
                    return a.start - b.start;
                }
            });
            // List to represent rooms
            List<Schedule> rooms = new ArrayList<Schedule>();
            for (int i = 0; i < intervals.length; i++) {
                boolean scheduled = false;
                for (int j = 0; j < rooms.size(); j++) {
                    // For each room, if we find a idle room, we put this interval in this room (by updating end time of room's schedule)
                    if (intervals[i].start >= rooms.get(j).end) {
                        rooms.get(j).end = intervals[i].end;
                        scheduled = true;
                        break;
                    }
                }
                // if we can not put this interval in any of room (or room number is 0), we create a new room
                if (!scheduled) {
                    rooms.add(new Schedule(intervals[i].end));
                }
            }
            return rooms.size();
        }
    }

  • 0
    C

    Wouldn't this be O(n*2) ?


Log in to reply
 

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