Share My Java O(n) solution without sort


  • 0
    Z

    /**
    * @see {@link AlgorithmicCrush#AlgorithmicCrush()}
    * the basic idea is generate an array, put result[start] += 1, put result[end] += -1,
    * add all the number in the array, if once sum > 1, means there is conflict
    * @param intervals
    * @return
    */
    public boolean canAttendMeetings(Interval[] intervals) {
    int max = 0;
    for(Interval i : intervals) {
    max = Math.max(i.end, max);
    }
    int[] result = new int[max + 1];
    for(Interval i : intervals) {
    result[i.start] += 1;
    result[i.end] += -1;
    }
    int sum = 0;
    for(int i = 0; i < result.length; i++) {
    sum += result[i];
    if(sum > 1) {
    return false;
    }
    }
    return true;
    }


  • 0
    G

    What if interval.end=INT_MAX? You may gg then,


Log in to reply
 

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