Non-overlapping Intervals: Optimizing Interval Arrangement

The "Non-overlapping Intervals" problem is a key challenge in interval manipulation, focusing on minimizing overlaps in a set of intervals.

Problem Statement

Given an array of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example

• Input: Intervals [[1,2],[2,3],[3,4],[1,3]] Output: 1 Explanation: Removing the interval [1,3] leaves [1,2], [2,3], and [3,4], which are non-overlapping.

Greedy Solution Approach

Breaking Down the Solution

• Sort by End Time: Sort the intervals by their end times to ensure a minimal number of removals.
• Count Removals: Iterate through the intervals, counting each time an interval overlaps with the previous one.
• Update End Time: After a non-overlapping interval is found, update the end time for the next comparison.

Conclusion

The Non-overlapping Intervals problem is an excellent application of greedy algorithms in optimizing interval arrangements. It highlights the importance of strategic sorting and interval selection in minimizing removals and is a common scenario in resource allocation and scheduling systems.

Rust Solution

Rust's sort_by_key(|a| a[1]) sorts the intervals in place by extracting each one's end time through a closure, rather than the explicit (a, b) => a[1] - b[1] comparator the JS version writes. Because the Vec<Vec<i32>> parameter arrives immutable, let mut intervals = intervals shadows it with a mut binding so the in-place sort compiles — you cannot mutate a value that wasn't bound with mut. The early exit uses intervals.is_empty(), and the function yields count as a bare tail expression (no return) with a fixed-width i32 return type.

Go Solution

Go's sort.Slice takes a less-function func(i, j int) bool that receives indices, so its body compares intervals[i][1] < intervals[j][1] positionally instead of returning the numeric difference a JS comparator would. end and count are introduced with :=, letting the compiler infer their int type from the initialiser, and the input stays a plain [][]int slice-of-slices with no generic annotation. The overlap tally advances with count++, which in Go is a statement rather than an expression.