aboutsummaryrefslogtreecommitdiff
path: root/non_overlapping_interval.c
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /non_overlapping_interval.c
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'non_overlapping_interval.c')
-rw-r--r--non_overlapping_interval.c30
1 files changed, 30 insertions, 0 deletions
diff --git a/non_overlapping_interval.c b/non_overlapping_interval.c
new file mode 100644
index 0000000..c9f0288
--- /dev/null
+++ b/non_overlapping_interval.c
@@ -0,0 +1,30 @@
+// 435. Non-overlapping Intervals
+#include <stdbool.h>
+#include <stdlib.h>
+
+/*
+ * given an array of intervals 'intervals' where 'intervals[i] = [start[i],
+ * end[i]]', return the minimum number of intervals you need to remove to make
+ * the rest of the intervals non-overlapping
+ */
+
+int cmp(const void **a, const void **b) {
+ int *a1 = *(int **)a;
+ int *b1 = *(int **)b;
+ if (a1[1] == b1[1])
+ return a1[0] - b1[0];
+ return a1[1] - b1[1];
+}
+
+int eraseOverlapIntervals(int **intervals, int intervals_size,
+ int *intervals_col_size) {
+ qsort(intervals, intervals_size, sizeof(int *), cmp);
+ int k = intervals[0][1], ans = 0;
+ for (int i = 1; i < intervals_size; i++) {
+ if (intervals[i][0] < k)
+ ans++;
+ else
+ k = intervals[i][1];
+ }
+ return ans;
+}