Heap

64. K Closest Points to Origin

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        priority_queue<pair<double, pair<int, int>>, 
            vector<pair<double, pair<int, int>>>, 
            greater<>> pq;
        for (auto p : points) {
            double d = sqrt(pow(p[0], 2) + pow(p[1], 2));
            pq.push({d, {p[0], p[1]}});
        }
        vector<vector<int>> results;
        while (k > 0 && pq.size()) {
            k--;
            results.push_back({pq.top().second.first, pq.top().second.second});
            pq.pop();
        }
        return results;
    }
};

class Solution {
    private class Point implements Comparable<Point> {
        public int x;
        public int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public double distance() {
            return Math.sqrt(x*x + y*y);
        }

        @Override
        public int compareTo(Point that) {
            if (this.distance() < that.distance()) {
                return -1;
            } else {
                return 1;
            }
        }
    }

    // or pass it to the priority queue
    private class MyComparator implements Comparator<Point> {
        @Override
        public int compare(Point a, Point b) {
            if (b.distance() - a.distance() > 0) {
                return -1;
            } else {
                return 1;
            }
        }
    }

    public int[][] kClosest(int[][] points, int k) {
        PriorityQueue<Point> pq = new PriorityQueue<>();
        for (int[] p : points) {
            pq.offer(new Point(p[0], p[1]));
        }
        List<Point> results = new ArrayList<>();
        while (k > 0 && !pq.isEmpty()) {
            k--;
            results.add(pq.poll());
        }
        return results
                 .stream()
                 .map(p -> new int[] {p.x, p.y})
                 .toArray(int[][]::new);
    }
}

65. Find Median from Data Stream

TODO

66. Merge k Sorted Lists

TODO

67. 621. Task Scheduler

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        int freq[26];
        for (char task : tasks) {
            freq[task - 'A']++;
        }
        sort(begin(freq), end(freq));
        int chunk = freq[25] - 1;
        int slots = chunk * n;
        for (int i = 24; i>=0; i--){
            slots -= min(chunk, freq[i]);
        }
        // note that the slots might be negative when types of tasks are more than the n
        // and total number of tasks is larger than chunk * n.
        // eg., n = 2, tasks = ['A','A','A','B','B','B','C','C','C']
        return max(tasks.size(), tasks.size() + slots);
    }
};