Here's another quite clever method originating with Itzik Ben-Gan. Unfortunately, I don't believe that the original link is still active but I used the technique myself in this article (with attribution of course).

Calculating Gaps Between Overlapping Time Intervals in SQL[/url]

Using Jason's test data:

WITH C1 AS

(

-- Since the data table contains rows with a start and end date, we'll first unpivot

-- those using CROSS APPLY VALUES and assign a type to each. The columns e and s will

-- either be NULL (s NULL for an end date, e NULL for a start date) or row numbers

-- sequenced by the time. UserID has been eliminated because we're looking for overlapping

-- intervals across all users.

SELECT PatientID, ts, [Type], Cost

,e=CASE [Type]

WHEN 1 THEN NULL

ELSE ROW_NUMBER() OVER (PARTITION BY PatientID, [Type] ORDER BY DischargeDate) END

,s=CASE [Type]

WHEN -1 THEN NULL

ELSE ROW_NUMBER() OVER (PARTITION BY PatientID, [Type] ORDER BY AdmissionDate) END

FROM #PatientProblem

CROSS APPLY (VALUES (1, AdmissionDate-1), (-1, DischargeDate+1)) a([Type], ts)

),

C2 AS

(

-- Add a row number ordered as shown

SELECT C1.*, se=ROW_NUMBER() OVER (PARTITION BY PatientID ORDER BY ts, [Type] DESC)

FROM C1

),

C3 AS

(

-- Create a grpnm that pairs the rows

SELECT ts, grpnm=FLOOR((ROW_NUMBER() OVER (PARTITION BY PatientID ORDER BY ts)-1) / 2 + 1), PatientID, Cost

FROM C2

-- This filter is the magic that eliminates the overlaps

WHERE COALESCE(s-(se-s)-1, (se-e)-e) = 0

),

C4 AS

(

-- Grouping by grpnm restores the records to only non-overlapped intervals

-- *** Adjust intervals back to original

SELECT AdmissionDate=MIN(ts)+1, DischargeDate=MAX(ts)-1, PatientID, Cost=SUM(Cost)

FROM C3

GROUP BY PatientID, grpnm

)

SELECT PatientID, AdmissionDate, DischargeDate

-- *** Subquery to compute the cost

,Cost =

(

SELECT SUM(Cost)

FROM #PatientProblem b

WHERE a.PatientID = b.PatientID AND

b.AdmissionDate >= a.AdmissionDate AND

b.DischargeDate <= a.DischargeDate

)

FROM C4 a

ORDER BY PatientID, AdmissionDate;

You should find this approach to be pretty fast. I had to make just a couple of modifications to handle the 1 day apart issue between your end/start date overlaps (*** commented).