Welcome back, Sujit Kumar Mishra

Coding Question – Merge Overlapping Time Slots

Given the following time slots:

[(1,3), (2,6), (8,10), (15,18)]

Each time slot contains:

- First value → Start time

- Second value → End time

Question:

Write a Java program to merge the overlapping time slots and print the final merged intervals. Also, determine how many final merged slots remain after merging.

Additionally, explain your complete approach in detail, including:

1: The logic used to identify overlapping intervals

2: Step-by-step execution flow

3: Low-level implementation details

4: Time and space complexity of the solution

import java.util.*;

public class MergeIntervals {
    public static void main(String[] args) {
        // Input time slots
        int[][] intervals = { {1,3}, {2,6}, {8,10}, {15,18} };

        // Step 1: Sort intervals by start time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        // Step 2: Use a list to store merged intervals
        List<int[]> merged = new ArrayList<>();

        for (int[] interval : intervals) {
            // If merged list is empty OR no overlap, add interval
            if (merged.isEmpty() || 
                        merged.get(merged.size()-1)[1] < interval[0]) {
                merged.add(interval);
            } else {
                // Overlap: merge by updating end time
                merged.get(merged.size()-1)[1] = 
                 Math.max(merged.get(merged.size()-1)[1], interval[1]);
            }
        }

        // Printing merged intervals
        System.out.print("Merged intervals: ");
        for (int[] m : merged) {
            System.out.print("[" + m[0] + "," + m[1] + "] ");
        }
        System.out.println("\nNumber of merged slots: "
                                        + merged.size());
    }
}     

Approach Explanation (Simple Steps):

1: Sort the intervals by their start time.

2: This makes it easy to compare each interval with the previous one.

3: Iterate through the sorted intervals:

• If the current interval does not overlap with the previous (merged) interval, add it to the result.
• If it overlaps (i.e., current start ≤ previous end), merge them by updating the end time to the maximum of both ends.

4: Continue merging until all intervals are checked.

5: Print the merged intervals and count.

Logic to Identify Overlapping Intervals:

• Two intervals [a, b] and [c, d] overlap if c ≤ b.
• If they overlap, update the end to max(b, d).

Step-by-Step Execution Flow:

1: Input: [(1,3), (2,6), (8,10), (15,18)]

2: After sorting: [(1,3), (2,6), (8,10), (15,18)] (already sorted)

3: Merge:

• (1,3) and (2,6) overlap → merge to (1,6)
• (1,6) and (8,10) do not overlap → add (8,10)
• (8,10) and (15,18) do not overlap → add (15,18)

4: Final merged intervals: [(1,6), (8,10), (15,18)]

5: Number of merged slots: 3

Low-Level Implementation Details:

• Sorting: Use Arrays.sort() with a custom comparator.
• Merging: Use an ArrayList to dynamically add or update intervals.
• Output: Print intervals and their count.

Time and Space Complexity:

• Time Complexity:Sorting: O(n log n)
• Merging: O(n)
• Total: O(n log n)
• Space Complexity:O(n) for storing merged intervals.

Summary:

Sort the intervals, merge overlapping ones, and print the result. This method is easy to remember and efficient for interview or practical use.