Posts tagged as “sorting”

花花酱 LeetCode 1626. Best Team With No Conflicts

By zxi on October 18, 2020

You are the manager of a basketball team. For the upcoming tournament, you want to choose the team with the highest overall score. The score of the team is the sum of scores of all the players in the team.

However, the basketball team is not allowed to have conflicts. A conflict exists if a younger player has a strictly higher score than an older player. A conflict does not occur between players of the same age.

Given two lists, scores and ages, where each scores[i] and ages[i] represents the score and age of the i^th player, respectively, return the highest overall score of all possible basketball teams.

Example 1:

Input: scores = [1,3,5,10,15], ages = [1,2,3,4,5]
Output: 34
Explanation: You can choose all the players.

Example 2:

Input: scores = [4,5,6,5], ages = [2,1,2,1]
Output: 16
Explanation: It is best to choose the last 3 players. Notice that you are allowed to choose multiple people of the same age.

Example 3:

Input: scores = [1,2,3,5], ages = [8,9,10,1]
Output: 6
Explanation: It is best to choose the first 3 players.

Constraints:

1 <= scores.length, ages.length <= 1000
scores.length == ages.length
1 <= scores[i] <= 10⁶
1 <= ages[i] <= 1000

Solution: Sort + DP

Sort by (age, score) in descending order. For j < i, age[j] >= age[i]

dp[i] = max(dp[j] | score[j] >= score[i], j < i) + score[i]

Basically, we want to find the player j with best score among [0, i), and make sure score[i] <= score[j] (since age[j] >= age[i]) then we won’t have any conflicts.

ans = max(dp)

C++

// Author: Huahua

class Solution {

public:

int bestTeamScore(vector<int>& scores, vector<int>& ages) {

const int n = scores.size();

vector<pair<int, int>> players(n);

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

players[i] = {ages[i], scores[i]};

sort(rbegin(players), rend(players));

// dp[i] = max score of the first i players, i must be selected.

vector<int> dp(n);

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

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

if (players[i].second <= players[j].second)

dp[i] = max(dp[i], dp[j]);

dp[i] += players[i].second;

}

return *max_element(begin(dp), end(dp));

}

};

花花酱 LeetCode 1604. Alert Using Same Key-Card Three or More Times in a One Hour Period

By zxi on October 3, 2020

Leetcode company workers use key-cards to unlock office doors. Each time a worker uses their key-card, the security system saves the worker’s name and the time when it was used. The system emits an alert if any worker uses the key-card three or more times in a one-hour period.

You are given a list of strings keyName and keyTime where [keyName[i], keyTime[i]] corresponds to a person’s name and the time when their key-card was used in a single day.

Access times are given in the 24-hour time format “HH:MM”, such as "23:51" and "09:49".

Return a list of unique worker names who received an alert for frequent keycard use. Sort the names in ascending order alphabetically.

Notice that "10:00" – "11:00" is considered to be within a one-hour period, while "23:51" – "00:10" is not considered to be within a one-hour period.

Example 1:

Input: keyName = ["daniel","daniel","daniel","luis","luis","luis","luis"], keyTime = ["10:00","10:40","11:00","09:00","11:00","13:00","15:00"]
Output: ["daniel"]
Explanation: "daniel" used the keycard 3 times in a one-hour period ("10:00","10:40", "11:00").

Example 2:

Input: keyName = ["alice","alice","alice","bob","bob","bob","bob"], keyTime = ["12:01","12:00","18:00","21:00","21:20","21:30","23:00"]
Output: ["bob"]
Explanation: "bob" used the keycard 3 times in a one-hour period ("21:00","21:20", "21:30").

Example 3:

Input: keyName = ["john","john","john"], keyTime = ["23:58","23:59","00:01"]
Output: []

Example 4:

Input: keyName = ["leslie","leslie","leslie","clare","clare","clare","clare"], keyTime = ["13:00","13:20","14:00","18:00","18:51","19:30","19:49"]
Output: ["clare","leslie"]

Constraints:

1 <= keyName.length, keyTime.length <= 10⁵
keyName.length == keyTime.length
keyTime are in the format “HH:MM”.
[keyName[i], keyTime[i]] is unique.
1 <= keyName[i].length <= 10
keyName[i] contains only lowercase English letters.

Solution: Hashtable + sorting

Time complexity: O(nlogn)
Space complexity: O(n)

C++

class Solution {

public:

vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) {

unordered_map<string, vector<int>> t; // {name -> time}

for (size_t i = 0; i < keyName.size(); ++i) {

const int h = stoi(keyTime[i].substr(0, 2));

const int m = stoi(keyTime[i].substr(3));

t[keyName[i]].push_back(h * 60 + m);

}

vector<string> ans;

for (auto& [name, times] : t) {

sort(begin(times), end(times));

for (size_t i = 2; i < times.size(); ++i)

if (times[i] - times[i - 2] <= 60) {

ans.push_back(name);

break;

}

sort(begin(ans), end(ans));

return ans;

}

};

花花酱 LeetCode 1471. The k Strongest Values in an Array

By zxi on June 6, 2020

Given an array of integers arr and an integer k.

Return a list of the strongest k values in the array. return the answer in any arbitrary order.

Median is the middle value in an ordered integer list. More formally, if the length of the list is n, the median is the element in position ((n - 1) / 2) in the sorted list (0-indexed).

For arr = [6, -3, 7, 2, 11], n = 5 and the median is obtained by sorting the array arr = [-3, 2, 6, 7, 11] and the median is arr[m] where m = ((5 - 1) / 2) = 2. The median is 6.
For arr = [-7, 22, 17, 3], n = 4 and the median is obtained by sorting the array arr = [-7, 3, 17, 22] and the median is arr[m] where m = ((4 - 1) / 2) = 1. The median is 3.

Example 1:

Input: arr = [1,2,3,4,5], k = 2
Output: [5,1]
Explanation: Median is 3, the elements of the array sorted by the strongest are [5,1,4,2,3]. The strongest 2 elements are [5, 1]. [1, 5] is also accepted answer.
Please note that although |5 - 3| == |1 - 3| but 5 is stronger than 1 because 5 > 1.

Example 2:

Input: arr = [1,1,3,5,5], k = 2
Output: [5,5]
Explanation: Median is 3, the elements of the array sorted by the strongest are [5,5,1,1,3]. The strongest 2 elements are [5, 5].

Example 3:

Input: arr = [6,7,11,7,6,8], k = 5
Output: [11,8,6,6,7]
Explanation: Median is 7, the elements of the array sorted by the strongest are [11,8,6,6,7,7].
Any permutation of [11,8,6,6,7] is accepted.

Example 4:

Input: arr = [6,-3,7,2,11], k = 3
Output: [-3,11,2]

Example 5:

Input: arr = [-7,22,17,3], k = 2
Output: [22,17]

Constraints:

1 <= arr.length <= 10^5
-10^5 <= arr[i] <= 10^5
1 <= k <= arr.length

Solution 1: quick selection + sort

Step 1: find the median element m
Step 2: Sort the array according to m
Step 3: output the first k elements of the sorted array.

Time complexity: O(nlogn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> getStrongest(vector<int>& arr, int k) {

const int n = arr.size();

const int i = (n - 1) / 2;

// sort(begin(arr), end(arr));

nth_element(begin(arr), begin(arr) + i, end(arr));

const int m = arr[i];

sort(begin(arr), end(arr), [&](const int x, const int y) {

return abs(x - m) != abs(y - m) ? abs(x - m) > abs(y - m) : x > y;

});

return {begin(arr), begin(arr) + k};

}

};

花花酱 LeetCode 1366. Rank Teams by Votes

By zxi on March 2, 2020

In a special ranking system, each voter gives a rank from highest to lowest to all teams participated in the competition.

The ordering of teams is decided by who received the most position-one votes. If two or more teams tie in the first position, we consider the second position to resolve the conflict, if they tie again, we continue this process until the ties are resolved. If two or more teams are still tied after considering all positions, we rank them alphabetically based on their team letter.

Given an array of strings votes which is the votes of all voters in the ranking systems. Sort all teams according to the ranking system described above.

Return a string of all teams sorted by the ranking system.

Example 1:

Input: votes = ["ABC","ACB","ABC","ACB","ACB"]
Output: "ACB"
Explanation: Team A was ranked first place by 5 voters. No other team was voted as first place so team A is the first team.
Team B was ranked second by 2 voters and was ranked third by 3 voters.
Team C was ranked second by 3 voters and was ranked third by 2 voters.
As most of the voters ranked C second, team C is the second team and team B is the third.

Example 2:

Input: votes = ["WXYZ","XYZW"]
Output: "XWYZ"
Explanation: X is the winner due to tie-breaking rule. X has same votes as W for the first position but X has one vote as second position while W doesn't have any votes as second position.

Example 3:

Input: votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]
Output: "ZMNAGUEDSJYLBOPHRQICWFXTVK"
Explanation: Only one voter so his votes are used for the ranking.

Example 4:

Input: votes = ["BCA","CAB","CBA","ABC","ACB","BAC"]
Output: "ABC"
Explanation: 
Team A was ranked first by 2 voters, second by 2 voters and third by 2 voters.
Team B was ranked first by 2 voters, second by 2 voters and third by 2 voters.
Team C was ranked first by 2 voters, second by 2 voters and third by 2 voters.
There is a tie and we rank teams ascending by their IDs.

Example 5:

Input: votes = ["M","M","M","M"]
Output: "M"
Explanation: Only team M in the competition so it has the first rank.

Constraints:

1 <= votes.length <= 1000
1 <= votes[i].length <= 26
votes[i].length == votes[j].length for 0 <= i, j < votes.length.
votes[i][j] is an English upper-case letter.
All characters of votes[i] are unique.
All the characters that occur in votes[0] also occur in votes[j] where 1 <= j < votes.length.

Solution: Sort by rank

Time complexity: O(v*n + n^2*logn)
Space complexity: O(n*n)

C++

// Author: Huahua

class Solution {

public:

string rankTeams(vector<string>& votes) {

const int n = votes[0].length();

string ans(votes[0]);

vector<vector<int>> rank(26, vector<int>(n));

for (const auto& vote : votes)

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

++rank[vote[i] - 'A'][i];

sort(begin(ans), end(ans), [&](const char i, const char j) {

if (rank[i - 'A'] != rank[j - 'A']) return rank[i - 'A'] > rank[j - 'A'];

return i < j;

});

return ans;

}

};

花花酱 LeetCode 1348. Tweet Counts Per Frequency

By zxi on February 29, 2020

Implement the class TweetCounts that supports two methods:

1. recordTweet(string tweetName, int time)

Stores the tweetName at the recorded time (in seconds).

2. getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime)

Returns the total number of occurrences for the given tweetName per minute, hour, or day (depending on freq) starting from the startTime (in seconds) and ending at the endTime (in seconds).
freq is always minute, hour or day, representing the time interval to get the total number of occurrences for the given tweetName.
The first time interval always starts from the startTime, so the time intervals are [startTime, startTime + delta*1>, [startTime + delta*1, startTime + delta*2>, [startTime + delta*2, startTime + delta*3>, ... , [startTime + delta*i, min(startTime + delta*(i+1), endTime + 1)> for some non-negative number i and delta (which depends on freq).

Example:

Input
["TweetCounts","recordTweet","recordTweet","recordTweet","getTweetCountsPerFrequency","getTweetCountsPerFrequency","recordTweet","getTweetCountsPerFrequency"]
[[],["tweet3",0],["tweet3",60],["tweet3",10],["minute","tweet3",0,59],["minute","tweet3",0,60],["tweet3",120],["hour","tweet3",0,210]]

Output
[null,null,null,null,[2]
[2,1],null,[4]]

Explanation
TweetCounts tweetCounts = new TweetCounts();
tweetCounts.recordTweet("tweet3", 0);
tweetCounts.recordTweet("tweet3", 60);
tweetCounts.recordTweet("tweet3", 10);                             // All tweets correspond to "tweet3" with recorded times at 0, 10 and 60.
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 59); // return [2]. The frequency is per minute (60 seconds), so there is one interval of time: 1) [0, 60> - > 2 tweets.
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 60); // return [2, 1]. The frequency is per minute (60 seconds), so there are two intervals of time: 1) [0, 60> - > 2 tweets, and 2) [60,61> - > 1 tweet.
tweetCounts.recordTweet("tweet3", 120);                            // All tweets correspond to "tweet3" with recorded times at 0, 10, 60 and 120.
tweetCounts.getTweetCountsPerFrequency("hour", "tweet3", 0, 210);  // return [4]. The frequency is per hour (3600 seconds), so there is one interval of time: 1) [0, 211> - > 4 tweets.

Constraints:

There will be at most 10000 operations considering both recordTweet and getTweetCountsPerFrequency.
0 <= time, startTime, endTime <= 10^9

Solution: Hashtable + binary search

Time complexity:
Record: O(logn)
getCount: O(logn + |entries|)

Space complexity: O(n)

C++

// Author: Huahua

class TweetCounts {

public:

TweetCounts() {

m_.clear();

}

void recordTweet(string tweetName, int time) {

m_[tweetName].insert(time);

}

vector<int> getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) {

auto tit = m_.find(tweetName);

if (tit == m_.end()) return {};

const set<int>& s = tit->second;

int delta = 1;

if (freq == "minute") delta = 60;

else if (freq == "hour") delta = 60 * 60;

else if (freq == "day") delta = 60 * 60 * 24;

int slots = (endTime - startTime + delta - 1) / delta;

vector<int> ans(slots);

for (int i = startTime; i <= endTime; i += delta) {

auto it1 = s.lower_bound(i);

auto it2 = s.lower_bound(min(i + delta, endTime + 1));

ans.push_back(distance(it1, it2)); // O(|entries|)

}

return ans;

}

private:

unordered_map<string, set<int>> m_;

};