Posts tagged as “time”

花花酱 LeetCode 2224. Minimum Number of Operations to Convert Time

By zxi on April 2, 2022

You are given two strings current and correct representing two 24-hour times.

24-hour times are formatted as "HH:MM", where HH is between 00 and 23, and MM is between 00 and 59. The earliest 24-hour time is 00:00, and the latest is 23:59.

In one operation you can increase the time current by 1, 5, 15, or 60 minutes. You can perform this operation any number of times.

Return the minimum number of operations needed to convert current to correct.

Example 1:

Input: current = "02:30", correct = "04:35"
Output: 3
Explanation:
We can convert current to correct in 3 operations as follows:
- Add 60 minutes to current. current becomes "03:30".
- Add 60 minutes to current. current becomes "04:30".
- Add 5 minutes to current. current becomes "04:35".
It can be proven that it is not possible to convert current to correct in fewer than 3 operations.

Example 2:

Input: current = "11:00", correct = "11:01"
Output: 1
Explanation: We only have to add one minute to current, so the minimum number of operations needed is 1.

Constraints:

current and correct are in the format "HH:MM"
current <= correct

Solution: Greedy

Start with 60, then 15, 5 and finally increase 1 minute a time.

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

C++

// Author: Huahua

class Solution {

public:

int convertTime(string current, string correct) {

auto getMinute = [](string_view t) {

return (t[0] - '0') * 10 * 60

+ (t[1] - '0') * 60

+ (t[3] - '0') * 10

+ (t[4] - '0');

};

int t1 = getMinute(current);

int t2 = getMinute(correct);

int ans = 0;

for (int d : {60, 15, 5, 1})

while (t2 - t1 >= d) {

++ans;

t1 += d;

}

return ans;

}

};

花花酱 LeetCode 1904. The Number of Full Rounds You Have Played

By zxi on August 15, 2021

A new online video game has been released, and in this video game, there are 15-minute rounds scheduled every quarter-hour period. This means that at HH:00, HH:15, HH:30 and HH:45, a new round starts, where HH represents an integer number from 00 to 23. A 24-hour clock is used, so the earliest time in the day is 00:00 and the latest is 23:59.

Given two strings startTime and finishTime in the format "HH:MM" representing the exact time you started and finished playing the game, respectively, calculate the number of full rounds that you played during your game session.

For example, if startTime = "05:20" and finishTime = "05:59" this means you played only one full round from 05:30 to 05:45. You did not play the full round from 05:15 to 05:30 because you started after the round began, and you did not play the full round from 05:45 to 06:00 because you stopped before the round ended.

If finishTime is earlier than startTime, this means you have played overnight (from startTime to the midnight and from midnight to finishTime).

Return the number of full rounds that you have played if you had started playing at startTime and finished at finishTime.

Example 1:

Input: startTime = "12:01", finishTime = "12:44"
Output: 1
Explanation: You played one full round from 12:15 to 12:30.
You did not play the full round from 12:00 to 12:15 because you started playing at 12:01 after it began.
You did not play the full round from 12:30 to 12:45 because you stopped playing at 12:44 before it ended.

Example 2:

Input: startTime = "20:00", finishTime = "06:00"
Output: 40
Explanation: You played 16 full rounds from 20:00 to 00:00 and 24 full rounds from 00:00 to 06:00.
16 + 24 = 40.

Example 3:

Input: startTime = "00:00", finishTime = "23:59"
Output: 95
Explanation: You played 4 full rounds each hour except for the last hour where you played 3 full rounds.

Constraints:

startTime and finishTime are in the format HH:MM.
00 <= HH <= 23
00 <= MM <= 59
startTime and finishTime are not equal.

Solution: String / Simple math

ans = max(0, floor(end / 15) – ceil(start / 15))

Tips:

Write a reusable function to parse time to minutes.
a / b for floor, (a + b – 1) / b for ceil

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

C++

// Author: Huahua

class Solution {

public:

int numberOfRounds(string startTime, string finishTime) {

auto parseTime = [](string t) {

return ((t[0] - '0') * 10 + (t[1] - '0')) * 60 + (t[3] - '0') * 10 + t[4] - '0';

};

int m1 = parseTime(startTime);

int m2 = parseTime(finishTime);

if (m2 < m1) m2 += 24 * 60;

return max(0, m2 / 15 - (m1 + 14) / 15);

}

};

花花酱 LeetCode 1701. Average Waiting Time

By zxi on December 26, 2020

There is a restaurant with a single chef. You are given an array customers, where customers[i] = [arrival_i, time_i]:

arrival_i is the arrival time of the i^th customer. The arrival times are sorted in non-decreasing order.
time_i is the time needed to prepare the order of the i^th customer.

When a customer arrives, he gives the chef his order, and the chef starts preparing it once he is idle. The customer waits till the chef finishes preparing his order. The chef does not prepare food for more than one customer at a time. The chef prepares food for customers in the order they were given in the input.

Return the average waiting time of all customers. Solutions within 10^-5 from the actual answer are considered accepted.

Example 1:

Input: customers = [[1,2],[2,5],[4,3]]
Output: 5.00000
Explanation:
1) The first customer arrives at time 1, the chef takes his order and starts preparing it immediately at time 1, and finishes at time 3, so the waiting time of the first customer is 3 - 1 = 2.
2) The second customer arrives at time 2, the chef takes his order and starts preparing it at time 3, and finishes at time 8, so the waiting time of the second customer is 8 - 2 = 6.
3) The third customer arrives at time 4, the chef takes his order and starts preparing it at time 8, and finishes at time 11, so the waiting time of the third customer is 11 - 4 = 7.
So the average waiting time = (2 + 6 + 7) / 3 = 5.

Example 2:

Input: customers = [[5,2],[5,4],[10,3],[20,1]]
Output: 3.25000
Explanation:
1) The first customer arrives at time 5, the chef takes his order and starts preparing it immediately at time 5, and finishes at time 7, so the waiting time of the first customer is 7 - 5 = 2.
2) The second customer arrives at time 5, the chef takes his order and starts preparing it at time 7, and finishes at time 11, so the waiting time of the second customer is 11 - 5 = 6.
3) The third customer arrives at time 10, the chef takes his order and starts preparing it at time 11, and finishes at time 14, so the waiting time of the third customer is 14 - 10 = 4.
4) The fourth customer arrives at time 20, the chef takes his order and starts preparing it immediately at time 20, and finishes at time 21, so the waiting time of the fourth customer is 21 - 20 = 1.
So the average waiting time = (2 + 6 + 4 + 1) / 4 = 3.25.

Constraints:

1 <= customers.length <= 10⁵
1 <= arrival_i, time_i <= 10⁴
arrival_i<= arrival_i+1

Solution: Simulation

When a customer arrives, if the arrival time is greater than current, then advance the clock to arrival time. Advance the clock by cooking time. Waiting time = current time – arrival time.

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

C++

// Author: Huahua

class Solution {

public:

double averageWaitingTime(vector<vector<int>>& customers) {

int t = 0;

double w = 0;

for (const auto& c : customers) {

if (c[0] > t) t = c[0];

t += c[1];

w += t - c[0];

}

return w / customers.size();

}

};

Python3

# Author: Huahua

class Solution:

def averageWaitingTime(self, customers: List[List[int]]) -> float:

cur = 0

waiting = 0

for arrival, time in customers:

cur = max(cur, arrival) + time

waiting += cur - arrival

return waiting / len(customers)

花花酱 LeetCode 539. Minimum Time Difference

By zxi on March 21, 2018

Problem

Given a list of 24-hour clock time points in “Hour:Minutes” format, find the minimum minutes difference between any two time points in the list.

Example 1:

Input: ["23:59","00:00"]
Output: 1

Note:

The number of time points in the given list is at least 2 and won’t exceed 20000.
The input time is legal and ranges from 00:00 to 23:59.

Solution

Time complexity: O(nlog1440)

Space complexity: O(n)

C++

// Author: huahua

// Running time: 16 ms

class Solution {

public:

int findMinDifference(vector<string>& timePoints) {

constexpr int kMins = 24 * 60;

set<int> seen;

for (const string& time : timePoints) {

int m = stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3));

if (!seen.insert(m).second) return 0;

}

int ans = (*seen.begin() - *seen.rbegin() + kMins) % kMins;

const int* l = nullptr;

for (const int& t : seen) {

if (l) ans = min(ans, t - *l);

l = &t;

}

return ans;

}

};

花花酱 LeetCode 309. Best Time to Buy and Sell Stock with Cooldown

By zxi on January 6, 2018

题目大意：给你每天的股价，没有交易次数限制，但是卖出后要休息一天才能再买进。问你最大收益是多少？

Say you have an array for which the i^th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

prices = [1, 2, 3, 0, 2]

maxProfit = 3

transactions = [buy, sell, cooldown, buy, sell]

Idea:

Solution:

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

int maxProfit(vector<int>& prices) {

int sold = 0;

int rest = 0;

int hold = INT_MIN;

for (const int price : prices) {

int prev_sold = sold;

sold = hold + price;

hold = max(hold, rest - price);

rest = max(rest, prev_sold);

}

return max(rest, sold);

}

};

Related Problems:

花花酱 LeetCode 121. Best Time to Buy and Sell Stock