diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /non_overlapping_interval.c | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'non_overlapping_interval.c')
-rw-r--r-- | non_overlapping_interval.c | 30 |
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; +} |