Posts published in “Greedy”

花花酱 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;

}

};

花花酱 LeetCode 822. Card Flipping Game

By zxi on April 29, 2018

Problem

题目大意：每张牌的正反面各印着一个数，你可以随便翻牌。找出一个最小的数使得其他牌当前正面的数值都不和它相等。

On a table are N cards, with a positive integer printed on the front and back of each card (possibly different).

We flip any number of cards, and after we choose one card.

If the number X on the back of the chosen card is not on the front of any card, then this number X is good.

What is the smallest number that is good? If no number is good, output 0.

Here, fronts[i] and backs[i] represent the number on the front and back of card i.

A flip swaps the front and back numbers, so the value on the front is now on the back and vice versa.

Example:

Input: fronts = [1,2,4,4,7], backs = [1,3,4,1,3]
Output: 2
Explanation: If we flip the second card, the fronts are [1,3,4,4,7] and the backs are [1,2,4,1,3]. We choose the second card, which has number 2 on the back, and it isn't on the front of any card, so 2 is good.

Note:

1 <= fronts.length == backs.length <= 1000.
1 <= fronts[i] <= 2000.
1 <= backs[i] <= 2000.

Solution: Hashset

C++

// Author: Huahua

// Running time: 23 ms

class Solution {

public:

int flipgame(vector<int>& fronts, vector<int>& backs) {

unordered_set<int> same;

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

if (fronts[i] == backs[i])

same.insert(fronts[i]);

int ans = INT_MAX;

for (int v : fronts)

if (v < ans && !same.count(v)) ans = v;

for (int v : backs)

if (v < ans && !same.count(v)) ans = v;

return ans == INT_MAX ? 0 : ans;

}

};

花花酱 LeetCode 807. Max Increase to Keep City Skyline

By zxi on March 24, 2018

Problem

题目大意：给你一个二维地图和每个坐标的大楼高度，求出总增高的最大值使得城市的天际线（投影）保持不变。

In a 2 dimensional array grid, each value grid[i][j] represents the height of a building located there. We are allowed to increase the height of any number of buildings, by any amount (the amounts can be different for different buildings). Height 0 is considered to be a building as well.

At the end, the “skyline” when viewed from all four directions of the grid, i.e. top, bottom, left, and right, must be the same as the skyline of the original grid. A city’s skyline is the outer contour of the rectangles formed by all the buildings when viewed from a distance. See the following example.

What is the maximum total sum that the height of the buildings can be increased?

Example:
Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
Output: 35
Explanation: 
The grid is:
[ [3, 0, 8, 4], 
  [2, 4, 5, 7],
  [9, 2, 6, 3],
  [0, 3, 1, 0] ]

The skyline viewed from top or bottom is: [9, 4, 8, 7]
The skyline viewed from left or right is: [8, 7, 9, 3]

The grid after increasing the height of buildings without affecting skylines is:

gridNew = [ [8, 4, 8, 7],
            [7, 4, 7, 7],
            [9, 4, 8, 7],
            [3, 3, 3, 3] ]

Notes:

1 < grid.length = grid[0].length <= 50.
All heights grid[i][j] are in the range [0, 100].
All buildings in grid[i][j] occupy the entire grid cell: that is, they are a 1 x 1 x grid[i][j] rectangular prism.

Solution: Greedy

Find the max of each row and column, increase the height of building at i,j to min(max_row[i], max_col[j]).

Time Complexity: O(m*n)

Space complexity: O(m+n)

C++

// Author: Huahua

class Solution {

public:

int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {

int m = grid.size();

int n = grid[0].size();

vector<int> x(n, 0);

vector<int> y(n, 0);

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

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

x[j] = max(x[j], grid[i][j]);

y[i] = max(y[i], grid[i][j]);

}

int ans = 0;

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

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

ans += min(x[i], y[j]) - grid[i][j];

return ans;

}

};

花花酱 LeetCode 575. Distribute Candies

By zxi on March 5, 2018

题目大意：有一些不同种类的糖果，男生女生各得一半数量的糖果，问女生最多可能得到多少种不同种类的糖果。

Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribute these candies equally in number to brother and sister. Return the maximum number of kinds of candies the sister could gain.

Example 1:

Input: candies = [1,1,2,2,3,3]

Output: 3

Explanation:

There are three different kinds of candies (1, 2 and 3), and two candies for each kind.

Optimal distribution: The sister has candies [1,2,3] and the brother has candies [1,2,3], too.

The sister has three different kinds of candies.

Example 2:

Input: candies = [1,1,2,3]

Output: 2

Explanation: For example, the sister has candies [2,3] and the brother has candies [1,1].

The sister has two different kinds of candies, the brother has only one kind of candies.

Note:

The length of the given array is in range [2, 10,000], and will be even.
The number in given array is in range [-100,000, 100,000].

Solution 1: Greedy

Give all unique candies to sisters until they have n/2 candies.

Time complexity: O(n)

Space complexity: O(n)

C++ Hashset

// Author: Huahua

// Running time: 258 ms

class Solution {

public:

int distributeCandies(vector<int>& candies) {

unordered_set<int> kinds(candies.begin(), candies.end());

return min(kinds.size(), candies.size() / 2);

}

};

C++ Bitset

// Author: Huahua

// Running time: 195 ms (beats 97.61%)

class Solution {

public:

int distributeCandies(vector<int>& candies) {

constexpr int kMaxKinds = 200001;

constexpr int kOffset = 100000;

bitset<kMaxKinds> s;

for (int candy : candies)

if (!s.test(candy + kOffset))

s.set(candy + kOffset);

return std::min(s.count(), candies.size() / 2);

}

};

花花酱 LeetCode 214. Shortest Palindrome

By zxi on February 20, 2018

题目大意：给你一个字符串你可以在它的前面添加一些字符，返回最短的回文字符串。

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

Solution 1: Brute Force

Time complexity: O(n^2)

Space complexity: O(n)

C++ w/ copy

// Author: Huahua

// Running time: 102 ms (<25.74%)

class Solution {

public:

string shortestPalindrome(string s) {

const string r(s.rbegin(), s.rend());

const int n = s.size();

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

if (s.substr(0, n - i) == r.substr(i))

return r.substr(0, i) + s;

return "";

}

};

C++ w/o copy

// Author: Huahua

// Running time: 13 ms (<49.74%)

class Solution {

public:

string shortestPalindrome(string s) {

const string r(s.rbegin(), s.rend());

const int n = s.size();

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

if (s.compare(0, n - i, r, i, n - i) == 0)

return r.substr(0, i) + s;

return "";

}

};