计算投影总长度

junlingpang

A    5    10
A    15    18
A    2    7
A    4    6
B    1    10
B    3    5
C    1    3
C    4    5
C    11    13

如上，第一列为标签（列间以tab分隔），其后两列可以看成是x轴上一条线段的两个端点，计算相同标签下线段的投影总长度（即不计算重叠的部分）。

以标签A为例：

最终A标签下线段投影总长度为10-2+18-15=11。

请大侠们指点一下怎么编程序解决吧。

谢谢啦^_^

yybmsrs

分情况一个个算？

junlingpang

回复 2# yybmsrs


    嗯，得考虑到每一种情况，思路有点儿乱，谢谢参与

iamlimeng

没严格测试，你看看是否正确。

1. #!/usr/bin/perl
   
2. 
   
3. use strict;
   
4. use warnings;
   
5. 
   
6. my %result;
   
7. while (<DATA>) {
   
8.         my ($key,$start,$end) = split /\s+/;
   
9.          foreach ($start+1 .. $end) {
   
10.                  $result{$key}{'count'}++ unless ($result{$key}{$_});
    
11.                  $result{$key}{$_} = 1;
    
12.          }
    
13. }
    
14. foreach (keys %result) {
    
15.         print "$_\t$result{$_}{'count'}\n";
    
16. }
    
17. 
    
18. <STDIN>;
    
19. 
    
20. __DATA__
    
21. A    5    10
    
22. A    15    18
    
23. A    2    7
    
24. A    4    6
    
25. B    1    10
    
26. B    3    5
    
27. C    1    3
    
28. C    4    5
    
29. C    11    13

复制代码

zhlong8

A 并 B = A + B - (A 交 B) 这个公式叫什么来着？可以用

junlingpang

回复 4# iamlimeng


    刚试了下，可以的，谢谢了
    我再好好研究研究，呵呵

junlingpang

回复 5# zhlong8


    嗯。对于两个的情况还行，多个并集可能实现起来有点儿麻烦。谢谢提供思路

zhlong8

回复  zhlong8


    嗯。对于两个的情况还行，多个并集可能实现起来有点儿麻烦。谢谢提供思路
junlingpang 发表于 2011-06-09 22:34

    对计算机来说多个和两个没有质的区别，它就是做重复运算的。而且写出来的程序具有通用性，抽象级别很高

junlingpang

回复 8# zhlong8


    嗯，我试一下，谢谢大侠

zhlong8

回复 9# junlingpang


    这是最简单的递归思路，其实数端点的方法更快