Posts tagged as “priority queue”

花花酱 LeetCode 502. IPO

By zxi on August 4, 2018

Problem

Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.

You are given several projects. For each project i, it has a pure profit P_i and a minimum capital of C_i is needed to start the corresponding project. Initially, you have W capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.

To sum up, pick a list of at most k distinct projects from given projects to maximize your final capital, and output your final maximized capital.

Example 1:

Input: k=2, W=0, Profits=[1,2,3], Capital=[0,1,1].

Output: 4

Explanation: Since your initial capital is 0, you can only start the project indexed 0.
             After finishing it you will obtain profit 1 and your capital becomes 1.
             With capital 1, you can either start the project indexed 1 or the project indexed 2.
             Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
             Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.

Note:

You may assume all numbers in the input are non-negative integers.
The length of Profits array and Capital array will not exceed 50,000.
The answer is guaranteed to fit in a 32-bit signed integer.

Solution: Greedy

For each round, find the most profitable job whose capital requirement <= W.

Finish that job and increase W.

Brute force (TLE)

Time complexity: O(kn)

Space complexity: O(1)

C++

class Solution {

public:

int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {

for (int i = 0; i < k; ++i) {

int best_j = -1;

int best_profit = 0;

for (int j = 0; j < Profits.size(); ++j) {

if (Capital[j] <= W && Profits[j] > best_profit) {

best_j = j;

best_profit = Profits[j];

}

if (best_profit == 0) break;

W += Profits[best_j];

Profits[best_j] = INT_MIN; // Used.

}

return W;

}

};

Use priority queue and multiset to track doable and undoable projects at given W.

Time complexity: O(nlogn)

Space complexity: O(n)

// Author: Huahua

// Running time: 28 ms (beats 96.4%)

class Solution {

public:

int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {

priority_queue<int> doable; // sorted by profit high to low.

multiset<pair<int, int>> undoable; // {capital, profit}

for (int i = 0; i < Profits.size(); ++i) {

if (Profits[i] <= 0) continue;

if (Capital[i] <= W)

doable.push(Profits[i]);

else

undoable.emplace(Capital[i], Profits[i]);

}

auto it = undoable.cbegin();

while (!doable.empty() && k--) {

W += doable.top(); doable.pop();

while (it != undoable.cend() && it->first <= W)

doable.push(it++->second);

}

return W;

}

};

Or use an array and sort by capital

// Author: Huahua

// Running time: 28 ms (beats 96.4%)

class Solution {

public:

int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {

priority_queue<int> doable; // sorted by profit high to low.

vector<pair<int, int>> undoable; // {capital, profit}

for (int i = 0; i < Profits.size(); ++i) {

if (Profits[i] <= 0) continue;

if (Capital[i] <= W)

doable.push(Profits[i]);

else

undoable.emplace_back(Capital[i], Profits[i]);

}

sort(begin(undoable), end(undoable));

auto it = undoable.cbegin();

while (!doable.empty() && k--) {

W += doable.top(); doable.pop();

while (it != undoable.cend() && it->first <= W)

doable.push(it++->second);

}

return W;

}

};

花花酱 LeetCode 871. Minimum Number of Refueling Stops

By zxi on July 14, 2018

Problem

A car travels from a starting position to a destination which is target miles east of the starting position.

Along the way, there are gas stations. Each station[i] represents a gas station that is station[i][0] miles east of the starting position, and has station[i][1] liters of gas.

The car starts with an infinite tank of gas, which initially has startFuel liters of fuel in it. It uses 1 liter of gas per 1 mile that it drives.

When the car reaches a gas station, it may stop and refuel, transferring all the gas from the station into the car.

What is the least number of refueling stops the car must make in order to reach its destination? If it cannot reach the destination, return -1.

Note that if the car reaches a gas station with 0 fuel left, the car can still refuel there. If the car reaches the destination with 0 fuel left, it is still considered to have arrived.

Example 1:

Input: target = 1, startFuel = 1, stations = []
Output: 0
Explanation: We can reach the target without refueling.

Example 2:

Input: target = 100, startFuel = 1, stations = [[10,100]]
Output: -1
Explanation: We can't reach the target (or even the first gas station).

Example 3:

Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
Output: 2
Explanation: 
We start with 10 liters of fuel.
We drive to position 10, expending 10 liters of fuel.  We refuel from 0 liters to 60 liters of gas.
Then, we drive from position 10 to position 60 (expending 50 liters of fuel),
and refuel from 10 liters to 50 liters of gas.  We then drive to and reach the target.
We made 2 refueling stops along the way, so we return 2.

Note:

1 <= target, startFuel, stations[i][1] <= 10^9
0 <= stations.length <= 500
0 < stations[0][0] < stations[1][0] < ... < stations[stations.length-1][0] < target

Solution1: DP

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 24 ms

class Solution {

public:

int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {

const int n = stations.size();

// dp[i]: max distance to go with i stops.

vector<long> dp(n + 1, startFuel);

// For each station

for (int i = 0; i < n; ++i)

// for j stops, start from high to low to avoid reusing station i

for (int j = i + 1; j >= 1; --j)

if (dp[j - 1] >= stations[i][0])

// if we can reach station i with j - 1 stops,

// we can reach dp[j - 1] + station[i][1] with j stops.

dp[j] = max(dp[j], dp[j - 1] + stations[i][1]);

for (int i = 0; i < dp.size(); ++i)

if (dp[i] >= target) return i;

return -1;

}

};

Solution2: Priority Queue

Time complexity: O(nlogn)

Space complexity: O(n)

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {

int cur = startFuel;

int stops = 0;

int i = 0;

priority_queue<int> q; // gas (high to low) of reachable stations.

while (true) {

if (cur >= target) return stops;

while (i < stations.size() && stations[i][0] <= cur)

q.push(stations[i++][1]);

if (q.empty()) break;

cur += q.top(); q.pop();

++stops;

}

return -1;

}

};

V2: Iterator

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {

int cur = startFuel;

int stops = 0;

priority_queue<int> q; // gas (high to low) of reachable stations.

auto it = begin(stations);

while (true) {

if (cur >= target) return stops;

while (it != end(stations) && it->at(0) <= cur)

q.push(it++->at(1));

if (q.empty()) break;

cur += q.top(); q.pop();

++stops;

}

return -1;

}

};

Solution 2: Priority queue / max heap

Time complexity: O(n) + O(nlogk)

Space complexity: O(n)

C++

// Author: Huahuas

// Running time: 16 ms

class Solution {

public:

vector<int> topKFrequent(vector<int>& nums, int k) {

unordered_map<int, int> count;

for (const int num : nums)

++count[num];

priority_queue<pair<int, int>> q;

for (const auto& pair : count) {

q.emplace(-pair.second, pair.first);

if (q.size() > k) q.pop();

}

vector<int> ans;

for (int i = 0; i < k; ++i) {

ans.push_back(q.top().second);

q.pop();

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 56 ms

class Solution {

public List<Integer> topKFrequent(int[] nums, int k) {

Map<Integer, Integer> counts = new HashMap<>();

for (int num : nums)

counts.put(num, counts.getOrDefault(num, 0) + 1);

PriorityQueue<int[]> queue = new PriorityQueue<>((x, y) -> x[0] - y[0]);

for (Integer num : counts.keySet()) {

queue.offer(new int[]{counts.get(num), num});

if (queue.size() > k) queue.poll();

}

List<Integer> ans = new ArrayList<>();

for (int i = 0; i < k; ++i)

ans.add(queue.poll()[1]);

return ans;

}

Python

"""

Author: Huahua

Running time: 56 ms

"""

class Solution:

def topKFrequent(self, nums, k):

counts = collections.Counter(nums)

h = []

for num in counts.keys():

heapq.heappush(h, (counts[num], num))

if len(h) > k: heapq.heappop(h)

return [heapq.heappop(h)[1] for i in range(k)]

Solution 3: Bucket Sort

Time complexity: O(n)

Space complexity: O(n)

C++/hashmap

class Solution {

public:

vector<int> topKFrequent(vector<int>& nums, int k) {

unordered_map<int, int> count;

int max_freq = 1;

for (const int num : nums)

max_freq = max(max_freq, ++count[num]);

map<int, vector<int>> buckets;

for (const auto& kv : count)

buckets[kv.second].push_back(kv.first);

vector<int> ans;

for (int i = max_freq; i >= 1; --i) {

auto it = buckets.find(i);

if (it == buckets.end()) continue;

ans.insert(ans.end(), it->second.begin(), it->second.end());

if (ans.size() == k) return ans;

}

return ans;

}

};

C++/array

class Solution {

public:

vector<int> topKFrequent(vector<int>& nums, int k) {

unordered_map<int, int> count;

for (const int num : nums)

++count[num];

vector<vector<int>> buckets(nums.size() + 1);

for (const auto& kv : count)

buckets[kv.second].push_back(kv.first);

vector<int> ans;

for (auto it = buckets.rbegin(); it != buckets.rend(); ++it) {

const vector<int>& keys = *it;

if (keys.empty()) continue;

ans.insert(ans.begin(), keys.begin(), keys.end());

if (ans.size() == k) return ans;

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 23 ms

class Solution {

public List<Integer> topKFrequent(int[] nums, int k) {

List[] buckets = new List[nums.length + 1];

Map<Integer, Integer> counts = new HashMap<>();

for (int num : nums)

counts.put(num, counts.getOrDefault(num, 0) + 1);

for (int num : counts.keySet()) {

int count = counts.get(num);

if (buckets[count] == null)

buckets[count] = new ArrayList<Integer>();

buckets[count].add(num);

}

List<Integer> ans = new ArrayList<>();

for (int i = buckets.length - 1; i > 0 && ans.size() < k; --i) {

if (buckets[i] != null) ans.addAll(buckets[i]);

}

return ans;

}

Python

"""

Author: Huahua

Running time: 64 ms

"""

class Solution:

def topKFrequent(self, nums, k):

counts = collections.Counter(nums)

buckets = [[] for _ in range(len(nums) + 1)]

for num in counts.keys():

buckets[counts[num]].append(num)

ans = []

for i in range(len(nums), 0, -1):

ans += buckets[i]

if len(ans) == k: return ans

return ans

Posts tagged as “priority queue”

花花酱 LeetCode 502. IPO

Problem

Solution: Greedy

花花酱 LeetCode 871. Minimum Number of Refueling Stops

Problem

Solution1: DP

Solution2: Priority Queue

Related Problems

花花酱 LeetCode 347. Top K Frequent Elements

Solution 2: Priority queue / max heap

C++

Java

Python

Solution 3: Bucket Sort

C++/hashmap

C++/array

Java

Python

Related Problems

花花酱 LeetCode 692. Top K Frequent Words

花花酱 LeetCode 295. Find Median from Data Stream O(logn) + O(1)