JAVA AC Solution, Greedy, beats 92.03%


  • 9
    S

    According to greedy, you get one interval, then add the one right behind it. Then recursively deal with the rest.

    public class Solution {
        public int minMeetingRooms(Interval[] intervals) {
            Arrays.sort(intervals, new Comparator<Interval>(){
               public int compare(Interval o1, Interval o2){
                   return o1.start - o2.start;
               } 
            });
            return helper(new ArrayList(Arrays.asList(intervals)));
        }
        
        private int helper(List<Interval> li){
            if(li.size() == 0)
                return 0;
            Interval pre = li.get(0);
            List<Interval> nextLi = new ArrayList();
            for(int i=1;i<li.size();i++){
                Interval inter = li.get(i);
                if(inter.start < pre.end){
                    nextLi.add(inter);
                }else{
                    pre = inter;
                }
            }
            return 1 + helper(nextLi);
        }
    }

  • 6
    Y

    I am a newer to Leetcode, can I ask what does AC mean? really see it in many places but not sure what does it mean?


  • 2
    S

    AC means Accept


  • 0
    Y

    oops, I thought it was a kind of algorithm,anyway, thank you for answering this.


  • 0
    D

    O(n!) time complexity?


  • 0
    L

    Why the algorithm sort the interval list by start time instead of finish time?


  • 2

    should be O(n^2) time complexity. And with heap we have O(nlogn) complexity. The result reminds us that the fast solution on OJ doesn't necessarily mean it has a better complexity.


Log in to reply
 

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