Algorithm: Leetcode Contest 400

3169. Count Days Without Meetings

solution

class Solution {
    public int countDays(int days, int[][] meetings) {
        // sort the meeting
        Arrays.sort(meetings, new Comparator<int[]>(){
            @Override
            public int compare(int[] meeting1, int[] meeting2) {
                return meeting1[0]- meeting2[0];
            }
        });

        List<int[]> consec = new ArrayList<>();
        for(int i = 0; i < meetings.length; i++) {
            int curStart = meetings[i][0];
            int curEnd = meetings[i][1];

            while(i + 1 < meetings.length && meetings[i + 1][0] <= curEnd) {
                curEnd = Math.max(curEnd, meetings[i + 1][1]);
                i++;
            }
            consec.add(new int[]{curStart, curEnd});
        }

        int sum = consec.get(0)[0] - 1;
        for(int i = 1; i < consec.size(); i++) {
            sum += consec.get(i)[0] - consec.get(i - 1)[1] - 1;
        }

        sum += days - consec.get(consec.size() - 1)[1];

        return sum;
        
    }
}

Retro

1. when encounter array problem, always think if the sorting can solve the problem.
2. how to extend the end time of a trunk

3170. Lexicographically Minimum String After Removing Stars

Solution

class Solution {
    public String clearStars(String s) {
        char[] chars = s.toCharArray();
        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node n1, Node n2) {
                if (n1.c != n2.c) {
                    return n1.c - n2.c;
                } else {
                    return n2.index - n1.index;
                }
            }
        });
        
        Node temp = null;
        for(int i = 0; i < chars.length; i++) {
            if (chars[i] != '*') {
                pq.add(new Node(chars[i], i));
            } else {
                // chars[i] == '*'
                if (pq.isEmpty()) {
                    continue;
                }
                temp = pq.poll();
                chars[temp.index] = '*';
            }
        }
        
        StringBuilder sb = new StringBuilder();
        
        for(char c: chars) {
            if (c != '*') {
                sb.append(c);
            }
        }
        
        return sb.toString();
        
    }
    
    class Node {
        char c;
        int index;
        
        public Node(char cc, int i) {
            c = cc;
            index = i;
        }
    }
}

Retro

1. the way to implement the comparator for Priority Queue.