performance-optimizer

Score Breakdown

Your Submission

{
  "explanation": "BOTTLENECK IDENTIFICATION:\n\n1. **Primary bottleneck: findPrevIndex linear scan (O(n) per call → O(n²) total)**. The original code performs a linear backward scan to find the latest non-overlapping item for each position. Since this is called n times in the DP loop and n times in backtracking, the total complexity is O(n²). This is the dominant bottleneck for the DP portion.\n\n2. **Secondary bottleneck: Conflict graph building (O(n²))**. The nested loop comparing every pair of items is O(n²). While the output size can be O(n²) in the worst case, a sweep-line approach reduces the overhead significantly for typical inputs.\n\nALGORITHMIC IMPROVEMENTS:\n\n1. **Binary search replaces linear scan**: Since items are sorted by end time, I pre-compute an `endTimes` array and use binary search to find the latest item ending at or before a given start time. This reduces findPrevIndex from O(n) to O(log n), making the entire DP phase O(n log n) instead of O(n²).\n\n2. **Pre-computed previous indices**: Instead of calling findPrevIndex on-the-fly (which was called both in the DP loop and backtracking), I pre-compute all `prevIndex[i]` values in a single O(n log n) pass. This eliminates redundant computation.\n\n3. **Sweep-line conflict graph with Set/Map**: Replaced the O(n²) nested loop with an event-based sweep line. Events (item starts/ends) are sorted by time. A `Set<string>` tracks currently active intervals. When a new item starts, it conflicts with all items in the active set. This is O(n log n + output) instead of O(n²) for sparse conflict graphs.\n\n4. **Efficient data structures**: Used `Map<string, Set<string>>` for the conflict graph to enable O(1) lookups and avoid duplicates. Used `Set<string>` for the active interval tracker in the sweep line.\n\nCOMPLEXITY ANALYSIS:\n- Original: O(n²) for both conflict graph and DP\n- Optimized: O(n log n) for DP, O(n log n + k) for conflict graph where k = number of conflicts\n- Space: O(n + k) for conflict graph, O(n) for DP arrays and indices\n\nMEASUREMENT STRATEGY:\nProfile the function with increasing input sizes (100, 1000, 10000 items) to confirm the O(n²) → O(n log n) improvement. The binary search optimization shows the biggest improvement on dense schedules where many items overlap, as the linear scan degrades most in those cases.",
  "optimized_code": "import { ScheduleItem, Resolution } from \"./types\";\n\nexport function resolveConflicts(items: ScheduleItem[]): Resolution {\n  const sorted = [...items].sort((a, b) => a.end - b.end);\n  const n = sorted.length;\n\n  if (n === 0) return { selectedIds: [], totalValue: 0, conflicts: {} };\n\n  // Pre-compute end times array for binary search\n  const endTimes: number[] = sorted.map(item => item.end);\n\n  // Build conflict graph using sweep line with Set for O(n log n + output) instead of O(n^2)\n  const conflictSets = new Map<string, Set<string>>();\n  for (const item of sorted) {\n    conflictSets.set(item.id, new Set<string>());\n  }\n\n  // Create timeline events and sort by time (end events before start events at same time)\n  type Event = { time: number; isEnd: boolean; item: ScheduleItem };\n  const events: Event[] = [];\n  for (const item of sorted) {\n    events.push({ time: item.start, isEnd: false, item });\n    events.push({ time: item.end, isEnd: true, item });\n  }\n  events.sort((a, b) => a.time - b.time || (a.isEnd ? -1 : 1));\n\n  // Sweep line: maintain active set of currently open intervals\n  const active = new Set<string>();\n  const activeMap = new Map<string, ScheduleItem>();\n\n  for (const event of events) {\n    if (!event.isEnd) {\n      // Start event: this item conflicts with all currently active items\n      for (const activeId of active) {\n        conflictSets.get(event.item.id)!.add(activeId);\n        conflictSets.get(activeId)!.add(event.item.id);\n      }\n      active.add(event.item.id);\n      activeMap.set(event.item.id, event.item);\n    } else {\n      // End event: remove from active set\n      active.delete(event.item.id);\n      activeMap.delete(event.item.id);\n    }\n  }\n\n  // Convert conflict Sets to Record<string, string[]>\n  const conflicts: Record<string, string[]> = {};\n  for (const [id, conflictSet] of conflictSets) {\n    conflicts[id] = Array.from(conflictSet);\n  }\n\n  // Binary search: find latest item ending at or before targetStart\n  // Replaces O(n) linear scan with O(log n) binary search\n  function binarySearchPrev(targetStart: number): number {\n    let lo = 0, hi = n - 1, result = -1;\n    while (lo <= hi) {\n      const mid = (lo + hi) >> 1;\n      if (endTimes[mid] <= targetStart) {\n        result = mid;\n        lo = mid + 1;\n      } else {\n        hi = mid - 1;\n      }\n    }\n    return result;\n  }\n\n  // Pre-compute previous compatible index for each item: O(n log n) total\n  const prevIndex: number[] = new Array(n);\n  for (let i = 0; i < n; i++) {\n    prevIndex[i] = binarySearchPrev(sorted[i].start);\n  }\n\n  // Weighted interval scheduling DP: O(n)\n  const dp: number[] = new Array(n).fill(0);\n  dp[0] = sorted[0].value;\n\n  for (let i = 1; i < n; i++) {\n    const prev = prevIndex[i];\n    const includeVal = sorted[i].value + (prev >= 0 ? dp[prev] : 0);\n    const excludeVal = dp[i - 1];\n    dp[i] = Math.max(includeVal, excludeVal);\n  }\n\n  // Backtrack to find selected items using pre-computed indices: O(n)\n  const selected: string[] = [];\n  let idx = n - 1;\n  while (idx >= 0) {\n    const prev = prevIndex[idx];\n    const includeVal = sorted[idx].value + (prev >= 0 ? dp[prev] : 0);\n    if (idx === 0 || includeVal > dp[idx - 1]) {\n      selected.push(sorted[idx].id);\n      idx = prev;\n    } else {\n      idx--;\n    }\n  }\n\n  return {\n    selectedIds: selected.reverse(),\n    totalValue: dp[n - 1],\n    conflicts,\n  };\n}"
}