add 1353

fishercoder1534 · fishercoder1534 · commit 50a77d884b6e · 2020-02-16T09:34:58.000-08:00
diff --git a/README.md b/README.md
@@ -8,6 +8,7 @@ _If you like this project, please leave me a star._ &#9733;
 
 |  #  |      Title     |   Solutions   | Video  | Difficulty  | Tag                   
 |-----|----------------|---------------|--------|-------------|-------------
+|1353|[Maximum Number of Events That Can Be Attended](https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1353.java) | |Medium|Greedy, Sort, Segment Tree|
 |1352|[Product of the Last K Numbers](https://leetcode.com/problems/product-of-the-last-k-numbers/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1352.java) | |Medium|Array, Design|
 |1351|[Count Negative Numbers in a Sorted Matrix](https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1351.java) | |Easy|Array, Binary Search|
 |1349|[Maximum Students Taking Exam](https://leetcode.com/problems/maximum-students-taking-exam/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1349.java) | |Hard|Dynamic Programming|
diff --git a/src/main/java/com/fishercoder/solutions/_1353.java b/src/main/java/com/fishercoder/solutions/_1353.java
@@ -0,0 +1,77 @@
+package com.fishercoder.solutions;
+
+import com.fishercoder.common.utils.CommonUtils;
+
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.PriorityQueue;
+
+/**
+ * 1353. Maximum Number of Events That Can Be Attended
+ *
+ * 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 <= events[i][0] <= events[i][1] <= 10^5
+ * */
+public class _1353 {
+    public static class Solution1 {
+        /**
+         * Credit: https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/discuss/510263/JavaC%2B%2BPython-Priority-Queue
+         *
+         * 1. Sort events by start time, if ties, by end time;
+         * 2. From day 1 to day 100,000, we add all events that start on this day into a priorityqueue,
+         * also, we remove the events that closed on this day from the priorityqueue;
+         * 3. attend the event that ends on this day (earliest, i.e. greedy) and pop it out of the priorityqueue
+         *
+         * */
+        public int maxEvents(int[][] events) {
+            Arrays.sort(events, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
+            PriorityQueue<Integer> heap = new PriorityQueue<>();
+            int maxEvents = 0;
+            int i = 0;
+            for (int day = 1; day <= 100000; day++) {
+                while (i < events.length && events[i][0] == day) {
+                    heap.offer(events[i++][1]);
+                }
+                while (heap.size() > 0 && heap.peek() < day) {
+                    heap.poll();
+                }
+                if (heap.size() > 0) {
+                    heap.poll();
+                    maxEvents++;
+                }
+            }
+            return maxEvents;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1353Test.java b/src/test/java/com/fishercoder/_1353Test.java
@@ -0,0 +1,73 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._1353;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _1353Test {
+    private static _1353.Solution1 solution1;
+    private static int[][] events;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1353.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        events = new int[][]{
+                {1, 2},
+                {2, 3},
+                {3, 4}
+        };
+        assertEquals(3, solution1.maxEvents(events));
+    }
+
+    @Test
+    public void test2() {
+        events = new int[][]{
+                {1, 2},
+                {2, 3},
+                {3, 4},
+                {1, 2}
+        };
+        assertEquals(4, solution1.maxEvents(events));
+    }
+
+    @Test
+    public void test3() {
+        events = new int[][]{
+                {1, 4},
+                {4, 4},
+                {2, 2},
+                {3, 4},
+                {1, 1}
+        };
+        assertEquals(4, solution1.maxEvents(events));
+    }
+
+    @Test
+    public void test4() {
+        events = new int[][]{
+                {1, 100000}
+        };
+        assertEquals(1, solution1.maxEvents(events));
+    }
+
+    @Test
+    public void test5() {
+        events = new int[][]{
+                {1, 1},
+                {1, 2},
+                {1, 3},
+                {1, 4},
+                {1, 5},
+                {1, 6},
+                {1, 7},
+        };
+        assertEquals(7, solution1.maxEvents(events));
+    }
+
+}
