Counting overlapping intervals + merging overlapping intervals

1

Please login or register to vote for this query.

(click on this box to dismiss)

Query to count overlapping intervals by counting starts and ends. Plus, query to merge overlapping intervals. The merge query can also be used to find intervals within intervals having specific number of overlaps. The query comes with tests and results generated by brute-force.

History of Science and Math

Q&A for people interested in the history and origins of science and mathematics

IF 1 = 1
BEGIN -- GENERATE STUFF
	BEGIN -- GENERATE #tests
		IF OBJECT_ID('tempdb..#tests') IS NOT NULL DROP TABLE #tests;
		CREATE TABLE #tests (
			id INT IDENTITY NOT NULL PRIMARY KEY,
			frstdate DATE,
			lastdate DATE
		);
		INSERT INTO #tests (frstdate, lastdate)
		SELECT DATEADD(DAY, rand1, mindate), DATEADD(DAY, rand1 + rand2, mindate)
		FROM (VALUES ('2014-01-01', '2019-01-01', 10)) AS v1(mindate, maxdate, rangesize)
		CROSS JOIN (VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)) m1(num)
		CROSS JOIN (VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)) m2(num)
		CROSS JOIN (VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)) m3(num)
		CROSS APPLY (VALUES (ABS(CHECKSUM(NEWID())) % (DATEDIFF(DAY, mindate, maxdate) - rangesize + 1), ABS(CHECKSUM(NEWID())) % rangesize)) AS v2(rand1, rand2);
	END;
	BEGIN -- GENERATE #result_overlap_counts
		IF OBJECT_ID('tempdb..#result_overlap_counts') IS NOT NULL DROP TABLE #result_overlap_counts;
		CREATE TABLE #result_overlap_counts (
			opoint DATE,
			ocount INT
		);
		WITH rcte(nthdate, maxdate) AS (
			SELECT MIN(frstdate), MAX(lastdate)
			FROM #tests
			UNION ALL
			SELECT DATEADD(DAY, 1, nthdate), maxdate
			FROM rcte
			WHERE nthdate <= maxdate
		)
		INSERT INTO #result_overlap_counts
		SELECT nthdate, COUNT(id)
		FROM rcte
		LEFT JOIN #tests ON nthdate BETWEEN frstdate AND lastdate
		GROUP BY nthdate
		OPTION (MAXRECURSION 2500);
	END;
	BEGIN -- GENERATE #result_overlap_ranges
		IF OBJECT_ID('tempdb..#result_overlap_ranges') IS NOT NULL DROP TABLE #result_overlap_ranges;
		CREATE TABLE #result_overlap_ranges (
			frstdate DATE,
			lastdate DATE
		);
		INSERT INTO #result_overlap_ranges(frstdate, lastdate)
		SELECT MIN(opoint), MAX(opoint)
		FROM (
			SELECT opoint, ocount, SUM(chg) OVER (ORDER BY opoint) AS grp
			FROM (
				SELECT opoint, ocount, CASE WHEN ocount = 0 AND LAG(ocount) OVER (ORDER BY opoint) = 0 THEN 0 WHEN ocount > 0 AND LAG(ocount) OVER (ORDER BY opoint) > 0 THEN 0 ELSE 1 END AS chg
				FROM #result_overlap_counts
			) AS q1
		) AS q2
		WHERE ocount > 0
		GROUP BY grp;
	END;
END;
BEGIN -- QUERY overlap_counts_1
	DECLARE @result_overlap_counts_1 TABLE (
		opoint DATE,
		ocount INT
	);
	WITH cte1(d, v) AS (
		SELECT frstdate, +1 FROM #tests UNION ALL
		SELECT DATEADD(DAY, 1, lastdate), -1 FROM #tests
	), cte2(d, c) AS (
		SELECT d, SUM(SUM(v)) OVER (ORDER BY d)
		FROM cte1
		GROUP BY d
	)
	INSERT INTO @result_overlap_counts_1
	SELECT *
	FROM cte2;
	SELECT 'extra' AS err, opoint, ocount FROM @result_overlap_counts_1 EXCEPT SELECT 'extra', opoint, ocount FROM #result_overlap_counts;
END;
BEGIN -- QUERY overlap_ranges_1
	DECLARE @result_overlap_ranges_1 TABLE (
		frstdate DATE,
		lastdate DATE
	);
	WITH cte1(d, v) AS (
		SELECT frstdate, +1 FROM #tests UNION ALL
		SELECT DATEADD(DAY, 1, lastdate), -1 FROM #tests
	), cte2(d, c) AS (
		SELECT d, SUM(SUM(v)) OVER (ORDER BY d)
		FROM cte1
		GROUP BY d
	), cte3(d, c, f) AS (
		SELECT d, c, CASE WHEN LAG(c) OVER (ORDER BY d) > 0 THEN 0 ELSE 1 END
		FROM cte2
	), cte4(d, c, g) AS (
		SELECT d, c, SUM(f) OVER (ORDER BY d)
		FROM cte3
	)
	INSERT INTO @result_overlap_ranges_1
	SELECT MIN(d), DATEADD(DAY, -1, MAX(d))
	FROM cte4
	GROUP BY g;
	SELECT 'extra' AS err, frstdate, lastdate FROM @result_overlap_ranges_1 EXCEPT SELECT 'extra', frstdate, lastdate FROM #result_overlap_ranges
	UNION ALL
	SELECT 'misng' AS err, frstdate, lastdate FROM #result_overlap_ranges EXCEPT SELECT 'misng', frstdate, lastdate FROM @result_overlap_ranges_1
END;
BEGIN -- QUERY overlap_ranges_2
	DECLARE @result_overlap_ranges_2 TABLE (
		frstdate DATE,
		lastdate DATE
	);
	WITH cte1(d, v) AS (
		SELECT frstdate, +1 FROM #tests UNION ALL
		SELECT DATEADD(DAY, 1, lastdate), -1 FROM #tests
	), cte2(d, v, c) AS (
		SELECT d, v, SUM(v) OVER (ORDER BY d, v DESC ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)
		FROM cte1
	), cte3(d, n) AS (
		SELECT d, ROW_NUMBER() OVER (ORDER BY d)
		FROM cte2
		WHERE c = 0 OR (c = 1 AND v = 1)
	)
	INSERT INTO @result_overlap_ranges_2
	SELECT MIN(d), DATEADD(DAY, -1, MAX(d))
	FROM cte3
	GROUP BY (n - 1) / 2;
	SELECT 'extra' AS err, frstdate, lastdate FROM @result_overlap_ranges_2 EXCEPT SELECT 'extra', frstdate, lastdate FROM #result_overlap_ranges
	UNION ALL
	SELECT 'misng' AS err, frstdate, lastdate FROM #result_overlap_ranges EXCEPT SELECT 'misng', frstdate, lastdate FROM @result_overlap_ranges_2
END;
BEGIN -- QUERY overlap_ranges_3
	DECLARE @result_overlap_ranges_3 TABLE (
		frstdate DATE,
		lastdate DATE
	);
	WITH cte1(a, b, f) AS (
		SELECT frstdate, lastdate, CASE WHEN DATEADD(DAY, 1, MAX(lastdate) OVER (ORDER BY frstdate ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING)) >= frstdate THEN 0 ELSE 1 END
		FROM #tests
	), cte2(a, b, g) AS (
		SELECT a, b, SUM(f) OVER (ORDER BY a)
		FROM cte1
	)
	INSERT INTO @result_overlap_ranges_3
	SELECT MIN(a), MAX(b)
	FROM cte2
	GROUP BY g;
	SELECT 'extra' AS err, frstdate, lastdate FROM @result_overlap_ranges_3 EXCEPT SELECT 'extra', frstdate, lastdate FROM #result_overlap_ranges
	UNION ALL
	SELECT 'misng' AS err, frstdate, lastdate FROM #result_overlap_ranges EXCEPT SELECT 'misng', frstdate, lastdate FROM @result_overlap_ranges_3
END;

Enter Parameters

Options:
Switch to meta site
loading Hold tight while we fetch your results