Business Analyst

It was direct DP easy problem which can be solved in big(n) time complexity.

This is medium rated problem, which can be solved using Hashmap, time complexity is big(n).

Sort the intervals:

Sort the input array intervals based on the start time of each interval (i.e., the first element of each pair). Sorting helps to process intervals sequentially, ensuring that we can easily check if the current interval overlaps with the previous one.

Sorting is done in O(n log n) time complexity, where n is the number of intervals.

Initialize an empty list for merged intervals:

Create an empty list merged where you will store the non-overlapping intervals.

Iterate through the sorted intervals:

For each interval, check if it overlaps with the last interval in the merged list:

If the list is empty, add the current interval to the merged list.

Otherwise, compare the current interval's start time with the end time of the last interval in the merged list:

If they overlap: This means the current interval's start time is less than or equal to the end time of the last merged interval. In this case, merge the two intervals. The merged interval's end time will be the maximum of the end times of the two intervals.

If they don't overlap: Simply add the current interval to the merged list as a new non-overlapping interval.

Return the merged intervals:

After iterating through all intervals, the merged list will contain the merged non-overlapping intervals.

Sort by End Point:

Sort the balloons based on their end points (xend). This helps in minimizing the number of arrows needed.

Greedy Approach:

Initialize arrow_count = 0 and last_shot_position = -∞.

Iterate through the sorted balloons:

If the current balloon starts after the last_shot_position, shoot a new arrow at the end of the current balloon (xend), and update last_shot_position to xend.

If the current balloon overlaps with the last shot arrow, no new arrow is needed.

Return the Arrow Count:

After processing all balloons, return arrow_count as the minimum number of arrows required.