Minimum Task Slots

You are given n tasks, each represented as an interval \( (start, end) \) where start and end denote the starting and finishing times respectively. Your task is to determine the minimum number of slots required to schedule all tasks such that no two overlapping tasks are assigned to the same slot.

Two tasks \( (s_1, e_1) \) and \( (s_2, e_2) \) are considered non-overlapping if \( e_1 \leq s_2 \) or \( e_2 \leq s_1 \). The problem can be solved using a greedy algorithm with a min-heap. First, sort the tasks by their start time, and then iteratively assign tasks to an available slot (or create a new slot if necessary). The number of slots corresponds to the maximum number of overlapping tasks at any point in time.

inputFormat

The first line of input contains a single integer \( n \) representing the number of tasks. Each of the following \( n \) lines contains two space-separated integers, \( start \) and \( end \), representing the start and end times of a task.

outputFormat

Output a single integer denoting the minimum number of slots required to execute all tasks without any overlap.

3
1 4
2 5
6 8

2