|
1 | 1 | packagecom.fishercoder.solutions; |
2 | 2 |
|
3 | | -importcom.fishercoder.common.utils.CommonUtils; |
4 | | - |
5 | 3 | importjava.util.Arrays; |
6 | | -importjava.util.Collections; |
7 | 4 | importjava.util.PriorityQueue; |
8 | 5 |
|
9 | | -/** |
10 | | - * 1353. Maximum Number of Events That Can Be Attended |
11 | | - * |
12 | | - * Given an array of events where events[i] = [startDayi, endDayi]. Every event i starts at startDayi and ends at endDayi. |
13 | | - * 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. |
14 | | - * Return the maximum number of events you can attend. |
15 | | - * |
16 | | - * Example 1: |
17 | | - * Input: events = [[1,2],[2,3],[3,4]] |
18 | | - * Output: 3 |
19 | | - * Explanation: You can attend all the three events. |
20 | | - * One way to attend them all is as shown. |
21 | | - * Attend the first event on day 1. |
22 | | - * Attend the second event on day 2. |
23 | | - * Attend the third event on day 3. |
24 | | - * |
25 | | - * Example 2: |
26 | | - * Input: events= [[1,2],[2,3],[3,4],[1,2]] |
27 | | - * Output: 4 |
28 | | - * |
29 | | - * Example 3: |
30 | | - * Input: events = [[1,4],[4,4],[2,2],[3,4],[1,1]] |
31 | | - * Output: 4 |
32 | | - * |
33 | | - * Example 4: |
34 | | - * Input: events = [[1,100000]] |
35 | | - * Output: 1 |
36 | | - * |
37 | | - * Example 5: |
38 | | - * Input: events = [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7]] |
39 | | - * Output: 7 |
40 | | - * |
41 | | - * Constraints: |
42 | | - * 1 <= events.length <= 10^5 |
43 | | - * events[i].length == 2 |
44 | | - * 1 <= events[i][0] <= events[i][1] <= 10^5 |
45 | | - * */ |
46 | 6 | publicclass_1353 { |
47 | 7 | publicstaticclassSolution1 { |
48 | 8 | /** |
49 | 9 | * Credit: https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/discuss/510263/JavaC%2B%2BPython-Priority-Queue |
50 | | - * |
| 10 | + * <p> |
51 | 11 | * 1. Sort events by start time, if ties, by end time; |
52 | 12 | * 2. From day 1 to day 100,000, we add all events that start on this day into a priorityqueue, |
53 | 13 | * also, we remove the events that closed on this day from the priorityqueue; |
54 | 14 | * 3. attend the event that ends on this day (earliest, i.e. greedy) and pop it out of the priorityqueue |
55 | | - * |
56 | | - * */ |
| 15 | + */ |
57 | 16 | publicintmaxEvents(int[][]events) { |
58 | 17 | Arrays.sort(events, (a,b) ->a[0] !=b[0] ?a[0] -b[0] :a[1] -b[1]); |
59 | 18 | PriorityQueue<Integer>heap =newPriorityQueue<>(); |
|