Non Overlapping Intervals

                                            
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });
        
        int count = 1;
        int end = intervals[0][1];
        
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] >= end) {
                count++;
                end = intervals[i][1];
            }
        }
        
        return intervals.size() - count;
    }
};

                                            
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

        int count = 0;
        int end = Integer.MIN_VALUE;

        for (int[] interval : intervals) {
            if (interval[0] >= end) {
                end = interval[1];
            } else {
                count++;
            }
        }

        return count;
    }
}

                                            
public class Solution {
    public int EraseOverlapIntervals(int[][] intervals) {
        if (intervals == null || intervals.Length == 0) {
            return 0;
        }
        
        Array.Sort(intervals, (a, b) => a[1] - b[1]);
        
        int count = 0;
        int end = intervals[0][1];
        
        for (int i = 1; i < intervals.Length; i++) {
            if (intervals[i][0] < end) {
                count++;
            } else {
                end = intervals[i][1];
            }
        }
        
        return count;
    }
}

                                            
/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function(intervals) {
    intervals.sort((a, b) => a[0] - b[0]);
    let count = 0;
    let prevEnd = intervals[0][1];
    
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < prevEnd) {
            count++;
            prevEnd = Math.min(prevEnd, intervals[i][1]);
        } else {
            prevEnd = intervals[i][1];
        }
    }
    
    return count;
};

                                            
function eraseOverlapIntervals(intervals: number[][]): number {
    intervals.sort((a, b) => a[1] - b[1]);
    let count = 0;
    let end = -Infinity;
    for (const interval of intervals) {
        if (interval[0] >= end) {
            end = interval[1];
        } else {
            count++;
        }
    }
    return count;
};

                                            
class Solution {
    func eraseOverlapIntervals(_ intervals: [[Int]]) -> Int {
        guard !intervals.isEmpty else {
            return 0
        }
        
        let sortedIntervals = intervals.sorted { $0[1] < $1[1] }
        
        var count = 1
        var end = sortedIntervals[0][1]
        
        for i in 1..<sortedIntervals.count {
            if sortedIntervals[i][0] >= end {
                count += 1
                end = sortedIntervals[i][1]
            }
        }
        
        return sortedIntervals.count - count
    }
}

                                            
class Solution {
    fun eraseOverlapIntervals(intervals: Array<IntArray>): Int {
        if (intervals.isEmpty()) return 0
        
        intervals.sortBy { it[1] }
        
        var end = intervals[0][1]
        var count = 0
        
        for (i in 1 until intervals.size) {
            if (intervals[i][0] < end) {
                count++
            } else {
                end = intervals[i][1]
            }
        }
        
        return count
    }
}

                                            
class Solution {
  int eraseOverlapIntervals(List<List<int>> intervals) {
    intervals.sort((a, b) => a[1] - b[1]);
    int end = intervals[0][1];
    int removeCount = 0;
    
    for (int i = 1; i < intervals.length; i++) {
      if (intervals[i][0] < end) {
        removeCount++;
      } else {
        end = intervals[i][1];
      }
    }
    
    return removeCount;
  }
}

                                            
func eraseOverlapIntervals(intervals [][]int) int {
    if len(intervals) == 0 {
        return 0
    }

    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][1] < intervals[j][1]
    })

    count := 1
    end := intervals[0][1]

    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] >= end {
            count++
            end = intervals[i][1]
        }
    }

    return len(intervals) - count
}

                                            
# @param {Integer[][]} intervals
# @return {Integer}
def erase_overlap_intervals(intervals)
    intervals.sort_by! { |interval| interval[1] }
    non_overlapping_count = 0
    end_time = intervals[0][1]
    
    (1...intervals.length).each do |i|
        if intervals[i][0] < end_time
            non_overlapping_count += 1
        else
            end_time = intervals[i][1]
        end
    end
    
    return non_overlapping_count
end

                                            
object Solution {
    def eraseOverlapIntervals(intervals: Array[Array[Int]]): Int = {
        if (intervals.isEmpty) return 0
        val sortedIntervals = intervals.sortBy(_.last)
        var count = 1
        var end = sortedIntervals.head(1)
        
        for (i <- 1 until sortedIntervals.length) {
            if (sortedIntervals(i)(0) >= end) {
                count += 1
                end = sortedIntervals(i)(1)
            }
        }
        
        intervals.length - count
    }
}

                                            
impl Solution {
    pub fn erase_overlap_intervals(intervals: Vec<Vec<i32>>) -> i32 {
        let mut intervals = intervals;
        intervals.sort_by(|a, b| a[1].cmp(&b[1]));
        
        let mut count = 0;
        let mut end = i32::MIN;
        
        for interval in intervals {
            if interval[0] >= end {
                end = interval[1];
            } else {
                count += 1;
            }
        }
        
        count
    }
}

Explanation

To solve this coding challenge, we need to ensure that the remaining intervals after removing some become non-overlapping. The plan of action involves sorting the intervals based on their starting times and then iteratively checking for overlaps to decide which intervals to remove.

Key Steps:

Sorting the Intervals : We first sort the intervals based on their starting times. This helps in easily detecting overlaps as we traverse the intervals sequentially.
Iterating Over Intervals : We then initialize a counter to keep track of the number of intervals we need to remove and set a variable to keep track of the endpoint of the previous interval.
Check for Overlaps : For each interval, starting from the second one, we check if the current interval's start time is less than the previous interval's end time. If it is, it means there is an overlap.
Handling Overlaps : For overlapping intervals, we need to increment our removal counter and update the end time of the interval that we keep. We always retain the interval with the smaller end time to maximize the number of non-overlapping intervals.
Updating Non-overlapping Interval End Time : If there is no overlap, we simply update our endpoint tracker to the current interval's end time.

Detailed Steps in Pseudocode

Initialization :

Sort the intervals by their start times.
Initialize a
counter

for tracking the number of removed intervals.
Initialize
previous_end

to the end time of the first interval.

Iteration :

For each interval starting from the second one:

Compare the current interval's start with
previous_end

.
If there's an overlap, increment
counter

and update
previous_end

to the minimum of
previous_end

and the current interval's end.
If no overlap, update
previous_end

to the current interval's end time.

Return the Result :

Return the counter value which represents the minimum number of intervals that need to be removed.

Pseudocode

                                            
# Sort the intervals based on their start times
SORT intervals BY start_time

# Initialize count of intervals to remove and the end time of the previous interval
count = 0
previous_end = intervals[0][1]

# Iterate through the sorted intervals starting from the second interval
FOR i FROM 1 TO intervals.length - 1:
    
    # If the current interval starts before the previous interval ends, there is an overlap
    IF intervals[i][0] < previous_end:
        
        # Increment the count of intervals to remove
        count += 1
        
        # Update the end time of the previous interval to the minimum of previous_end and the current interval's end
        previous_end = MIN(previous_end, intervals[i][1])
        
    ELSE:
        # No overlap, update the end time of the previous interval to the current interval's end time
        previous_end = intervals[i][1]
        
RETURN count

In this pseudocode:

SORT intervals BY start_time

uses a sorting algorithm to arrange the intervals by their starting times so that we can easily check for overlaps in a sequential manner.
FOR i FROM 1 TO intervals.length - 1:

iterates through the intervals starting from the second one because we're using the first interval's end time as the initial reference.
IF intervals[i][0] < previous_end:

checks if the current interval starts before the previous interval ends, indicating an overlap.
count += 1

increments the counter whenever an overlapping interval is found and removed.
previous_end = MIN(previous_end, intervals[i][1])

updates the previous interval's end time to keep the interval with the smaller end, maintaining maximum possible space for future intervals.
RETURN count

gives the final count of intervals that need to be removed to make the rest non-overlapping.

This method ensures we remove the minimum number of overlapping intervals by prioritizing the intervals that end the earliest.