Sponsored
Sponsored
In this approach, we use a two-pointer technique to traverse both lists of intervals simultaneously. We check for intersections between the intervals pointed by our two pointers. If there's an intersection, we record it. We then progress the pointer that points to the interval with the smaller endpoint. This ensures that we consider new overlapping possibilities as the intervals in each list are disjoint and sorted.
Time Complexity: O(n + m), where n and m are the number of intervals in the two lists. This is because we process each interval at most once.
Space Complexity: O(1), apart from the output space, since only a few variables are used.
1#include <stdio.h>
2#include <stdlib.h>
3
4int** intervalIntersection(int** A, int ASize, int* AColSize, int** B, int BSize, int* BColSize, int* returnSize, int** returnColumnSizes){
5 int a = 0, b = 0;
6 int capacity = 1000; // Initial capacity based on constraints
7 int** ans = (int**) malloc(sizeof(int*) * capacity);
8 *returnColumnSizes = (int*) malloc(sizeof(int) * capacity);
9 *returnSize = 0;
10 while (a < ASize && b < BSize) {
11 int start = fmax(A[a][0], B[b][0]);
12 int end = fmin(A[a][1], B[b][1]);
13 if (start <= end) {
14 if (*returnSize == capacity) {
15 capacity *= 2;
16 ans = (int**) realloc(ans, sizeof(int*) * capacity);
17 *returnColumnSizes = (int*) realloc(*returnColumnSizes, sizeof(int) * capacity);
18 }
19 ans[*returnSize] = (int*) malloc(sizeof(int) * 2);
20 ans[*returnSize][0] = start;
21 ans[*returnSize][1] = end;
22 (*returnColumnSizes)[*returnSize] = 2;
23 (*returnSize)++;
24 }
25 if (A[a][1] < B[b][1])
26 a++;
27 else
28 b++;
29 }
30 return ans;
31}We use pointers a and b to iterate over firstList and secondList respectively. We find the maximum start and minimum end for the current intervals pointed by these pointers to determine overlap. If there's an overlap, it is added to the result list. We move the pointer with the smaller endpoint to ensure progress.