Non-overlapping Intervals - Solution & Explanation

The greedy approach involves sorting the intervals by their end times. Then, we iterate through the sorted list and count the number of overlapping intervals to remove. The idea is to always pick the interval with the earliest end time, which leaves more room for the remaining intervals.

Steps:

1. Sort the intervals based on their end time.
2. Initialize a variable to keep track of the end of the last added interval.
3. Iterate through the sorted intervals and for each interval, check if it overlaps with the last added interval. If it does, increment the count of intervals to remove. If it doesn't, update the end time to the current interval's end time.

This C implementation sorts the intervals based on their end times using qsort. It then iterates through the sorted intervals, maintaining a count of the overlapping intervals to be removed and updating the end of the last included interval.

This approach utilizes dynamic programming to solve the problem. It is typically less efficient than the greedy method but serves as an illustrative illustration of tackling overlap problems using dp.

1. Sort intervals based on start time to ensure a consistent order for dp evaluation.
2. Define a dp array where dp[i] stores the maximum count of non-overlapping intervals up to i-th interval.
3. Initialize each dp[i] to 1 as each interval can at least be alone considered non-overlapping.
4. For each interval, check whether it can be included in the non-overlapping list built so far without causing overlap.
5. The answer will be determined by the maximum value in the dp array.

This C solution sorts the intervals by start time and uses a dp array to store the longest non-overlapping subsequence up to each interval. It checks each interval against those before it to see if it can be appended without leading to overlap.