1353. Maximum Number of Events That Can Be Attended #

Problem #

Given an array of events where events[i] = [startDayi, endDayi]. Every event i starts at startDayi and ends at endDayi.

You can attend an event i at any day d where startTimei <= d <= endTimei. Notice that you can only attend one event at any time d.

Return the maximum number of events you can attend.

Example 1:

Input: events = [[1,2],[2,3],[3,4]]
Output: 3
Explanation: You can attend all the three events.
One way to attend them all is as shown.
Attend the first event on day 1.
Attend the second event on day 2.
Attend the third event on day 3.

Example 2:

Input: events= [[1,2],[2,3],[3,4],[1,2]]
Output: 4

Example 3:

Input: events = [[1,4],[4,4],[2,2],[3,4],[1,1]]
Output: 4

Example 4:

Input: events = [[1,100000]]
Output: 1

Example 5:

Input: events = [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7]]
Output: 7

Constraints:

• 1 <= events.length <= 10^5
• events[i].length == 2
• 1 <= startDayi <= endDayi <= 10^5

Problem Summary #

Given an array events, where events[i] = [startDayi, endDayi] indicates that meeting i starts on startDayi and ends on endDayi. You can attend meeting i on any day d that satisfies startDayi <= d <= endDayi. Note that you can only attend one meeting per day. Return the maximum number of meetings you can attend.

Solution Ideas #

• For problems like meeting scheduling and activity scheduling, the first instinct is that they are greedy problems. First sort the meetings by start time in ascending order; if the start times are the same, then sort by end time in ascending order. The greedy strategy is to prioritize attending meetings that end earlier. Because a meeting with a later end time means the meeting lasts longer, attending meetings that are about to end first allows you to attend more meetings.
• Note that the data given in the problem represents days. When comparing sizes, it is best to convert them into coordinate points on a coordinate axis. For example, [1,2] means this meeting lasts 2 days; if represented on a coordinate axis, it is [0,2], where 0-1 represents the first day and 1-2 represents the second day. Therefore, when comparing meetings, you need to subtract one from the start time. After selecting this meeting, remember to exclude this day. For example, if the second day is selected, then the next comparison of start times needs to start from coordinate 2, because the time range of the second day is 1-2, so before comparing meetings in the next round, the start time needs to be increased by one. Scan each meeting time interval from left to right, choose meetings whose end time is greater than the start time, continuously accumulate the count, and after scanning all meetings, the final result is the maximum number of meetings that can be attended.
• There is a very nasty test case in the test data; see the last test case in the test file. This data has multiple meetings stacked on the same day, and their start times are exactly the same. This special case requires adding a condition to exclude it; see the continue condition in the code below.

Code #

package leetcode

import (
	"sort"
)

func maxEvents(events [][]int) int {
	sort.Slice(events, func(i, j int) bool {
		if events[i][0] == events[j][0] {
			return events[i][1] < events[j][1]
		}
		return events[i][0] < events[j][0]
	})
	attended, current := 1, events[0]
	for i := 1; i < len(events); i++ {
		prev, event := events[i-1], events[i]
		if event[0] == prev[0] && event[1] == prev[1] && event[1] == event[0] {
			continue
		}
		start, end := max(current[0], event[0]-1), max(current[1], event[1])
		if end-start > 0 {
			current[0] = start + 1
			current[1] = end
			attended++
		}
	}
	return attended
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}