Java O(n) time and O(1) space using bit manipulation


  • -8
    D
    public boolean canAttendMeetings(Interval[] intervals) {
        boolean[] timeLine = new boolean[1000000];// It should be a large integer based on ranges.
        for(Interval interval: intervals) {
            for(int i = interval.start; i< interval.end; i++) {
                if(timeLine[i] == true)
                    return false;
                timeLine[i] = true;
            }
        }
        return true;
    }

  • -1
    H

    Good idea. In case we may get overflow, we can use set instead!

    Update:
    LTE and MTE, damn!

    public boolean canAttendMeetings(Interval[] intervals) {
        HashSet<Integer> hs = new HashSet<Integer>();
        
        for(Interval temp : intervals){
            for(int i = temp.start; i < temp.end; i++){
                if(hs.contains(i)) return false;
                hs.add(i);
            }
        }
        
        return true;
    }

  • 0
    N

    圆屌,这个复杂度显然不是o(N). 你还说good idea。


  • 0
    V

    It is not at all O(n)! You scan all the range inside an interval. What if intervals are with double precision?


  • 2
    Z
    1. It's not O(n) time,

    2. It's not O(1) space, and...

    3. It's not bit manipulation.


  • 0
    B

    @ZGeng 23333


Log in to reply
 

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