Minimum Removals to Avoid Overlap

You are given a set of n projects, where each project is represented as an interval with a start time and an end time. Two projects overlap if their intervals intersect (i.e. for two intervals \( (s_1, e_1)\) and \( (s_2, e_2)\), they overlap if \( s_1 < e_2 \) and \( s_2 < e_1 \)).

Your task is to remove the minimum number of projects so that no two remaining projects overlap. A greedy algorithm that sorts the projects by their end times is an effective strategy to achieve this.

Example:

Input: [(1,3), (2,5), (4,6), (7,8)]
Output: 1

inputFormat

The first line contains an integer n (\( n \ge 0 \)), the number of projects. The next n lines each contain two space-separated integers s and e (with \( s < e \)) representing the start and end times of a project.

outputFormat

Output a single integer representing the minimum number of projects that must be removed to ensure that no two projects overlap.

4
1 3
2 5
4 6
7 8

1