Task Scheduler

Move zeroes:

class Solution {
    public void moveZeroes(int[] nums) {

        // 2 pointers
        // point i: record current
        // point pos: reocrd non zero    
        int pos = 0;
        for (int i = 0; i < nums.length; i++) {            
            if (nums[i] != 0) {
                nums[pos] = nums[i];
                pos++;
            }
        }

        while (pos < nums.length) {
            nums[pos] = 0;
            pos++;
        }        
    }
}

Add binary

• from end to start
• use carry

class Solution {
    public String addBinary(String a, String b) {

        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;        
        StringBuilder sb = new StringBuilder();

        while (i >= 0 || j >= 0) {
            int sum = carry;            
            if (i >= 0) sum += a.charAt(i--) - '0';
            if (j >= 0) sum += b.charAt(j--) - '0';
            sb.append(sum % 2);
            carry = sum / 2;                        
        }

        if (carry != 0) sb.append(carry);
        return sb.reverse().toString();
    }
}

Binary Tree Vertical Order Traversal

public List<List<Integer>> verticalOrder(TreeNode root) {
        // Write your code here
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }

        Map<Integer, List<Integer>> hash = new HashMap<>();
        Queue<Integer> qCol = new LinkedList<>();
        Queue<TreeNode> qNode = new LinkedList<>();

        qCol.offer(0);
        qNode.offer(root);

        while (!qCol.isEmpty()) {                      // bfs
            int c = qCol.poll();
            TreeNode node = qNode.poll();

            hash.putIfAbsent(c, new ArrayList<>());
            hash.get(c).add(node.val);

            if (node.left != null) {
                qCol.offer(c - 1);
                qNode.offer(node.left);
            }
            if (node.right != null) {
                qCol.offer(c + 1);
                qNode.offer(node.right);
            }
        }

        for (int i = Collections.min(hash.keySet()); i <= Collections.max(hash.keySet()); i++) {
            ans.add(hash.get(i));
        }
        return ans;
    }

Meeting Rooms ii

• sort by start time
• heap: track the earliest end meet
• append meeting if next meeting just follow the meeting the heap
• sweep line, merge interval, insert interval

class Solution {
    public int minMeetingRooms(Interval[] intervals) {

        if(intervals == null || intervals.length == 0) return 0;

        Arrays.sort(intervals, (i1, i2) -> (i1.start - i2.start));
        PriorityQueue<Interval> heap = new PriorityQueue<>(intervals.length, (i1, i2) -> (i1.end - i2.end));        

        heap.add(intervals[0]);

        for (int i = 1; i < intervals.length; i++) {    // NOTE: can not start from 0, cf merge interval. 
                                                        // 0 means, interval[0] will be added twice 

            Interval interval = heap.poll();            

            if (intervals[i].start >= interval.end) {
                interval.end = intervals[i].end;
            } else {
                heap.add(intervals[i]);
            }
            heap.add(interval);
        }

        return heap.size();
    }
}

public class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        if(intervals == null || intervals.length == 0) return 0;
        Arrays.sort(intervals, (a, b) -> (a.start - b.start));
        int max = 0;
        PriorityQueue<Interval> queue = new PriorityQueue<>(intervals.length, (a, b) -> (a.end - b.end));
        for(int i = 0; i < intervals.length; i++){
            while(!queue.isEmpty() && intervals[i].start >= queue.peek().end)
                queue.poll();
            queue.offer(intervals[i]);
            max = Math.max(max, queue.size());
        }
        return max;
    }
}

• sweep line

class Solution {

    private class Event {
    int time;
    int status;

    public Event(int time, int status) {
        this.time = time;
        this.status = status;
    }
}

    public int minMeetingRooms(Interval[] intervals) {

        List<Event> list = new ArrayList<>();

        for (Interval interval : intervals) {
            list.add(new Event(interval.start, 1));
            list.add(new Event(interval.end, 0));
        }

        Collections.sort(list,((e1, e2) -> 
                               (e1.time != e2.time ? e1.time - e2.time : e1.status - e2.status)));

        int count = 0;
        int max = 0;
        for (Event event : list) {
            if (event.status == 1) {
                count++;
            } else {
                count--;
            }
            max = Math.max(max, count);
        }
        return max;

    }
}

Meeting Room:

class Solution {
    public boolean canAttendMeetings(Interval[] intervals) {

        if (intervals == null || intervals.length == 0) return true;

        Arrays.sort(intervals, (a,b) -> a.start - b.start);
        Interval last = intervals[0];

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i].start < last.end) return false;
            last.end = Math.max(last.end, intervals[i].end);
        }

        return true;        
    }
}