The 18th China Jiliang University Programming Contest is approaching, Little Gyro wants to send plenty of messages by e-mail to invite people participating in the competition. However, Little Gyro only has one e-mail account (acm309@126.com) to send these messages. In order to invite more candidates as possible, Little Gyro needs your help. Given the whole time table of the e-mail messages Little Gyro wants to send, including the start time and the end time of each message, and it usually doesn’t take the same time when Little Gyro sending different e-mail messages. Besides, Little Gyro cannot send two or more messages at the same time. That means Little Gyro can send the next message only if the start time after the end time of the previous one. Now Little Gyro wants to know how many e-mail messages he can send to the competition candidates at most.
时间: 2024-01-11 14:01:59 浏览: 189
This problem can be solved using a greedy algorithm. First, we need to sort the messages by their end time in ascending order. Then, we can start sending messages from the earliest end time to the latest end time, and choose the message with the earliest start time that doesn't conflict with the previously sent messages. This ensures that we can send the maximum number of messages without conflicts.
Here is the pseudocode for the algorithm:
1. Sort the messages by their end time in ascending order.
2. Initialize a variable count to 0.
3. Initialize a variable prev_end to 0.
4. For each message in the sorted list:
a. If the start time of the message is greater than or equal to prev_end,
increment count and update prev_end to the end time of the message.
5. Return count.
The time complexity of this algorithm is O(nlogn), where n is the number of messages. This is due to the sorting step. The rest of the algorithm takes linear time.
Here is the Python code for the algorithm:
```python
def max_emails(messages):
messages.sort(key=lambda x: x[1]) # sort by end time
count = 0
prev_end = 0
for start, end in messages:
if start >= prev_end:
count += 1
prev_end = end
return count
```
We can call the function with a list of tuples representing the start and end times of the messages:
```python
messages = [(1, 3), (2, 5), (4, 7), (6, 9), (8, 10)]
print(max_emails(messages)) # output: 3
```
In this example, we can send at most 3 messages without conflicts.
阅读全文