Daily LeetCode – day0036 0646. Maximum Length of Pair Chain

// 0646. Maximum Length of Pair Chain
class Solution {
    public int findLongestChain(int[][] pairs) {
        PriorityQueue<Pair> pairPriorityQueue = new PriorityQueue<>((Pair p1, Pair p2) -> p1.right - p2.right);
        for (int[] pair : pairs) {
            pairPriorityQueue.offer(new Pair(pair[0], pair[1]));
        }
        int ans = 0;
        int currentRight = Integer.MIN_VALUE;
        while (!pairPriorityQueue.isEmpty()) {
            if (pairPriorityQueue.peek().left > currentRight) {
                ++ans;
                currentRight = pairPriorityQueue.peek().right;
            }
            pairPriorityQueue.poll();
        }
        return ans;
    }
}

class Pair {
    int left;
    int right;

    Pair(int left, int right) {
        this.left = left;
        this.right = right;
    }
}
学习笔记:
这是一道中等难度的题目,就是贪心算法看电影的类似题目。
这道题可以用排序来做,但是跑出来9ms。
然后我用了优先队列,就可以跑出8ms。
这道题其实我再08.19就做了,然后这次抽到后,我就尝试使用了新学到的TreeSet来做,但发现里面有些数组是重复的,我就用了特殊手段处理,重写了比较方法,让返回值永远不为0,就避免了重复放不进去的尴尬。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。