Posts published in “Greedy”

花花酱 LeetCode 605. Can Place Flowers

By zxi on June 28, 2018

Problem

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots – they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: True

Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2
Output: False

Note:

The input array won’t violate no-adjacent-flowers rule.
The input array size is in the range of [1, 20000].
n is a non-negative integer which won’t exceed the input array size.

Solution: Greedy

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 21 ms

class Solution {

public:

bool canPlaceFlowers(vector<int>& flowerbed, int n) {

int count = 0;

for (size_t i = 0; i < flowerbed.size() && count < n; ++i) {

if (flowerbed[i]) continue;

bool left = i == 0 ? true : !flowerbed[i - 1];

bool right = i == flowerbed.size() - 1 ? true : !flowerbed[i + 1];

if (left && right) {

flowerbed[i++] = 1;

++count;

}

return count == n;

}

};

花花酱 LeetCode 452. Minimum Number of Arrows to Burst Balloons

By zxi on June 23, 2018

Problem

There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it’s horizontal, y-coordinates don’t matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 10⁴ balloons.

An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with x_start and x_endbursts by an arrow shot at x if x_start ≤ x ≤ x_end. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.

Example:

Input:
[[10,16], [2,8], [1,6], [7,12]]

Output:
2

Explanation:
One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).

Solution: Sweep Line

Time complexity: O(nlogn)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 82 ms

class Solution {

public:

int findMinArrowShots(vector<pair<int, int>>& points) {

if (points.empty()) return 0;

sort(points.begin(), points.end(),

[&](const pair<int,int>& a, const pair<int,int>& b){

return a.second < b.second;

});

int right = points.front().second;

int ans = 1;

for (const auto& point : points) {

if (point.first > right) {

right = point.second;

++ans;

}

return ans;

}

};

Problem

题目大意：给你一些牌，问你能否分组，要求每组w张连续的牌。

https://leetcode.com/problems/hand-of-straights/description/

Alice has a hand of cards, given as an array of integers.

Now she wants to rearrange the cards into groups so that each group is size W, and consists of W consecutive cards.

Return true if and only if she can.

Example 1:

Input: hand = [1,2,3,6,2,3,4,7,8], W = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8].

Example 2:

Input: hand = [1,2,3,4,5], W = 4
Output: false
Explanation: Alice's hand can't be rearranged into groups of 4.

Note:

1 <= hand.length <= 10000
0 <= hand[i] <= 10^9
1 <= W <= hand.length

Solution: Greedy

Time complexity: O(nlogn)

Space complexity: O(n)

// Author: Huahua

// Running time: 65 ms

class Solution {

public:

bool isNStraightHand(vector<int>& hand, int W) {

map<int, int> counts;

for (int h : hand) ++counts[h];

while (!counts.empty()) {

auto it = counts.begin();

int start = it->first;

for (int j = 0; j < W; ++j) {

if (it == counts.end()

|| it->first != start + j) return false;

auto prev = it++;

if (--(prev->second) == 0)

counts.erase(prev);

}

return true;

}

};

花花酱 LeetCode 334. Increasing Triplet Subsequence

By zxi on May 28, 2018

Problem

题目大意：判断一个数组中是否存在长度为3的单调递增子序列。

Formally the function should:

Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples:
Given [1, 2, 3, 4, 5],
return true.

Given [5, 4, 3, 2, 1],
return false.

Credits:
Special thanks to @DjangoUnchained for adding this problem and creating all test cases.

Solution: Greedy

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

bool increasingTriplet(vector<int>& nums) {

int min1 = INT_MAX;

int min2 = INT_MAX;

for (int num : nums) {

if (num > min2) return true;

else if (num < min1) {

min1 = num;

} else if (num > min1 && num < min2) {

min2 = num;

}

return false;

}

};

花花酱 LeetCode 826. Most Profit Assigning Work

By zxi on April 29, 2018

Problem

We have jobs: difficulty[i] is the difficulty of the ith job, and profit[i] is the profit of the ith job.

Now we have some workers. worker[i] is the ability of the ith worker, which means that this worker can only complete a job with difficulty at most worker[i].

Every worker can be assigned at most one job, but one job can be completed multiple times.

For example, if 3 people attempt the same job that pays $1, then the total profit will be $3. If a worker cannot complete any job, his profit is $0.

What is the most profit we can make?

Example 1:

Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100 
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get profit of [20,20,30,30] seperately.

Notes:

1 <= difficulty.length = profit.length <= 10000
1 <= worker.length <= 10000
difficulty[i], profit[i], worker[i] are in range [1, 10^5]

Solution 1: Sorting + Two pointers

Time complexity: O(nlogn + mlogm)

Space complexity: O(n)

// Author: Huahua

// Running time: 90 ms

class Solution {

public:

int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {

const int n = difficulty.size();

vector<pair<int, int>> jobs; // difficulty, profit

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

jobs.emplace_back(difficulty[i], profit[i]);

std::sort(jobs.begin(), jobs.end());

std::sort(worker.begin(), worker.end());

int ans = 0;

int i = 0;

int best = 0;

for (int level : worker) {

while (i < n && level >= jobs[i].first)

best = max(best, jobs[i++].second);

ans += best;

}

return ans;

}

};

Solution 2: Bucket + Greedy

Key idea: for each difficulty D, find the most profit job whose requirement is <= D.

Three steps:

for each difficulty D, find the most profit job whose requirement is == D, best[D] = max{profit of difficulty D}.
if difficulty D – 1 can make more profit than difficulty D, best[D] = max(best[D], best[D – 1]).
The max profit each worker at skill level D can make is best[D].

Time complexity: O(n)

Space complexity: O(10000)

C++

// Author: Huahua

// Running time: 112 ms

class Solution {

public:

int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {

const int N = 100000;

// max profit at difficulty i

vector<int> max_profit(N + 1, 0);

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

max_profit[difficulty[i]] = max(max_profit[difficulty[i]], profit[i]);

for (int i = 2; i <= N; ++i)

max_profit[i] = max(max_profit[i], max_profit[i - 1]);

int ans = 0;

for (int level : worker)

ans += max_profit[level];

return ans;

}

};

C++ using map

// Author: Huahua

// Running time: 112 ms

class Solution {

public:

int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {

map<int, int> bests;

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

bests[difficulty[i]] = max(bests[difficulty[i]], profit[i]);

int best = 0;

for (auto it = bests.begin(); it != bests.end(); ++it)

it->second = best = max(it->second, best);

int ans = 0;

for (int level : worker)

ans += prev(bests.upper_bound(level))->second;

return ans;

}

};

Posts published in “Greedy”

花花酱 LeetCode 605. Can Place Flowers

Problem

Solution: Greedy

花花酱 LeetCode 452. Minimum Number of Arrows to Burst Balloons

Problem

Solution: Sweep Line

Related Problems

花花酱 LeetCode 846. Hand of Straights

Problem

Solution: Greedy

花花酱 LeetCode 334. Increasing Triplet Subsequence

Problem

Solution: Greedy

花花酱 LeetCode 826. Most Profit Assigning Work

Problem

Solution 1: Sorting + Two pointers

Solution 2: Bucket + Greedy